The Euclidean k-matching problem is NP-hard

Let G be a complete edge-weighted graph on n vertices. To each subset of vertices of G assign the cost of the minimum spanning tree of the subset as its weight. Suppose that n is a multiple of some fixed positive integer k . The k -matching problem is the problem of finding a partition of the vertices of G into k -sets (sets of k elements), that minimizes the sum of the weights of the k -sets. The case of k = 3 has been shown to be NP-hard [Johnsson et al., 1998]. In the Euclidean version, the vertices of G are points in the plane and the weight of an edge is the Euclidean distance between its endpoints. We call this problem the Euclidean k -matching problem. We show that, for every fixed k ≥ 3 , the Euclidean k -matching problem is NP-hard. This resolves an open problem in the literature and provides the first theoretical justification for the use of known heuristic methods in the case of k = 3 . We also show that the problem remains NP-hard if the trees are required to be paths.