Informace o publikaci
Crossing Number Is NP-Hard for Constant Path-Width (And Tree-Width)
| Autoři | |
|---|---|
| Rok publikování | 2024 |
| Druh | Článek ve sborníku |
| Konference | 35th International Symposium on Algorithms and Computation (ISAAC 2024) |
| Fakulta / Pracoviště MU | |
| Citace | |
| Doi | http://dx.doi.org/10.4230/LIPIcs.ISAAC.2024.40 |
| Klíčová slova | Graph Drawing; Crossing Number; Tree-width; Path-width |
| Popis | Crossing Number is a celebrated problem in graph drawing. It is known to be NP-complete since the 1980s, and fairly involved techniques were already required to show its fixed-parameter tractability when parameterized by the vertex cover number. In this paper we prove that computing exactly the crossing number is NP-hard even for graphs of path-width 12 (and as a result, for simple graphs of path-width 13 and tree-width 9). Thus, while tree-width and path-width have been very successful tools in many graph algorithm scenarios, our result shows that general crossing number computations unlikely (under P? NP) could be successfully tackled using graph decompositions of bounded width, what has been a "tantalizing open problem" [S. Cabello, Hardness of Approximation for Crossing Number, 2013] till now. |