The Euclidean $k$-Matching Problem is NP-hard
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866908582659751936 |
|---|---|
| author | Díaz-Báñez, José-Miguel Fabila-Monroy, Ruy Higes-López, José-Manuel Marín, Nestaly Pérez-Cutiño, Miguel-Angel Pérez-Lantero, Pablo |
| author_facet | Díaz-Báñez, José-Miguel Fabila-Monroy, Ruy Higes-López, José-Manuel Marín, Nestaly Pérez-Cutiño, Miguel-Angel Pérez-Lantero, Pablo |
| contents | 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, that minimizes the sum of the weights of the $k$-sets. The case $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 \ge 3$, the Euclidean $k$-matching 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 $k=3$. We also show that the problem remains NP-hard if the trees are required to be paths. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_15660 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | The Euclidean $k$-Matching Problem is NP-hard Díaz-Báñez, José-Miguel Fabila-Monroy, Ruy Higes-López, José-Manuel Marín, Nestaly Pérez-Cutiño, Miguel-Angel Pérez-Lantero, Pablo Computational Geometry 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, that minimizes the sum of the weights of the $k$-sets. The case $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 \ge 3$, the Euclidean $k$-matching 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 $k=3$. We also show that the problem remains NP-hard if the trees are required to be paths. |
| title | The Euclidean $k$-Matching Problem is NP-hard |
| topic | Computational Geometry |
| url | https://arxiv.org/abs/2502.15660 |