Crossing Number Is NP-Hard for Constant Path-Width (And
Tree-Width)

D 2024

Crossing Number Is NP-Hard for Constant Path-Width (And Tree-Width)

HLINĚNÝ, Petr a Liana KHAZALIYA

Základní údaje

Originální název

Crossing Number Is NP-Hard for Constant Path-Width (And Tree-Width)

Autoři

HLINĚNÝ, Petr a Liana KHAZALIYA

Vydání

LIPIcs Vol. 322. Dagstuhl, Germany, 35th International Symposium on Algorithms and Computation (ISAAC 2024), od s. "40:1"-"40:15", 15 s. 2024

Nakladatel

Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Německo

Utajení

není předmětem státního či obchodního tajemství

Forma vydání

elektronická verze "online"

Kód RIV

RIV/00216224:14330/24:00139112

Organizační jednotka

Fakulta informatiky

ISBN

978-3-95977-354-6

ISSN

DOI

https://doi.org/10.4230/LIPIcs.ISAAC.2024.40

EID Scopus

2-s2.0-85213030168

Klíčová slova anglicky

Graph Drawing; Crossing Number; Tree-width; Path-width

Štítky

core_A, firank_A

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 18. 3. 2025 13:55, prof. RNDr. Petr Hliněný, Ph.D.

Anotace

V originále

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.

Citovat

HLINĚNÝ, Petr a Liana KHAZALIYA. Crossing Number Is NP-Hard for Constant Path-Width (And Tree-Width). Online. In Mestre, Juli\'{a}n and Wirth, Anthony. 35th International Symposium on Algorithms and Computation (ISAAC 2024). LIPIcs Vol. 322. Dagstuhl, Germany: Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik, 2024, s. "40:1"-"40:15", 15 s. ISBN 978-3-95977-354-6. Dostupné z: https://doi.org/10.4230/LIPIcs.ISAAC.2024.40.

@inproceedings{2485007,
   author = {Hliněný, Petr and Khazaliya, Liana},
   address = {Dagstuhl, Germany},
   booktitle = {35th International Symposium on Algorithms and Computation (ISAAC 2024)},
   doi = {https://doi.org/10.4230/LIPIcs.ISAAC.2024.40},
   edition = {LIPIcs Vol. 322},
   editor = {Mestre, Juli\'{a}n and Wirth, Anthony},
   keywords = {Graph Drawing; Crossing Number; Tree-width; Path-width},
   howpublished = {elektronická verze "online"},
   language = {eng},
   location = {Dagstuhl, Germany},
   isbn = {978-3-95977-354-6},
   pages = {"40:1"-"40:15"},
   publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
   title = {Crossing Number Is NP-Hard for Constant Path-Width (And Tree-Width)},
   year = {2024}
}

TY  - CONF
ID  - 2485007
AU  - Hliněný, Petr - Khazaliya, Liana
PY  - 2024
TI  - Crossing Number Is NP-Hard for Constant Path-Width (And Tree-Width)
PB  - Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik
CY  - Dagstuhl, Germany
SN  - 9783959773546
KW  - Graph Drawing
KW  - Crossing Number
KW  - Tree-width
KW  - Path-width
N2  - 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.
ER  -

HLINĚNÝ, Petr a Liana KHAZALIYA. Crossing Number Is NP-Hard for Constant Path-Width (And Tree-Width). Online. In Mestre, Juli$\backslash$'$\{$a$\}$n and Wirth, Anthony. \textit{35th International Symposium on Algorithms and Computation (ISAAC 2024)}. LIPIcs Vol. 322. Dagstuhl, Germany: Schloss Dagstuhl -- Leibniz-Zentrum f$\{\backslash$''u$\}$r Informatik, 2024, s.~''40:1''-''40:15'', 15 s. ISBN~978-3-95977-354-6. Dostupné z: https://doi.org/10.4230/LIPIcs.ISAAC.2024.40.

Přehled o publikaci