Crossing Number is NP-hard for Constant Path-width (and Tree-width)
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915892899610624 |
|---|---|
| author | Hliněný, Petr Khazaliya, Liana |
| author_facet | Hliněný, Petr Khazaliya, Liana |
| contents | The crossing number of a graph is the minimum number of edge crossings that a graph can have when drawn in the plane. Determining this number, known as the Crossing Number problem, is a celebrated problem in combinatorial optimization. It has been known to be NP-complete since the 1980s, and already showing its fixed-parameter tractability when parameterized by the vertex cover number required fairly involved techniques. In this paper, we prove that computing the crossing number exactly remains NP-hard even for graphs of path-width 12 (and as a result, for simple graphs of path-width 13 and tree-width 9).
These results highlight that, although both path- and tree-decompositions have been highly successful tools in many graph algorithm scenarios, general crossing number computation is unlikely (under P $\neq$ NP) to be successfully tackled using graph decompositions of bounded width -- a question that had remained a 'tantalizing open problem' [S. Cabello, Hardness of Approximation for Crossing Number, 2013] till now. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_18933 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Crossing Number is NP-hard for Constant Path-width (and Tree-width) Hliněný, Petr Khazaliya, Liana Computational Geometry Discrete Mathematics 68R10 The crossing number of a graph is the minimum number of edge crossings that a graph can have when drawn in the plane. Determining this number, known as the Crossing Number problem, is a celebrated problem in combinatorial optimization. It has been known to be NP-complete since the 1980s, and already showing its fixed-parameter tractability when parameterized by the vertex cover number required fairly involved techniques. In this paper, we prove that computing the crossing number exactly remains NP-hard even for graphs of path-width 12 (and as a result, for simple graphs of path-width 13 and tree-width 9). These results highlight that, although both path- and tree-decompositions have been highly successful tools in many graph algorithm scenarios, general crossing number computation is unlikely (under P $\neq$ NP) to be successfully tackled using graph decompositions of bounded width -- a question that had remained a 'tantalizing open problem' [S. Cabello, Hardness of Approximation for Crossing Number, 2013] till now. |
| title | Crossing Number is NP-hard for Constant Path-width (and Tree-width) |
| topic | Computational Geometry Discrete Mathematics 68R10 |
| url | https://arxiv.org/abs/2406.18933 |