Treewidth Is NP-Complete on Cubic Graphs

Hans L. Bodlaender; Édouard Bonnet; Lars Jaffke; Dusan Knop; Paloma T. Lima; Martin Milanic; Sebastian Ordyniak; Sukanya Pandey; Ondrej Suchý

doi:10.4230/LIPICS.IPEC.2023.7

Treewidth Is NP-Complete on Cubic Graphs

Hans L. Bodlaender
, Édouard Bonnet
, Lars Jaffke
, Dusan Knop
, Paloma T. Lima
, Martin Milanic
, Sebastian Ordyniak
, Sukanya Pandey
, Ondrej Suchý

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

Abstract

In this paper, we show that Treewidth is NP-complete for cubic graphs, thereby improving the result by Bodlaender and Thilikos from 1997 that Treewidth is NP-complete on graphs with maximum degree at most 9. We add a new and simpler proof of the NP-completeness of treewidth, and show that Treewidth remains NP-complete on subcubic induced subgraphs of the infinite 3-dimensional grid.

Original language	English
Title of host publication	18th International Symposium on Parameterized and Exact Computation, IPEC 2023
Editors	Neeldhara Misra, Magnus Wahlström
Publisher	Schloss Dagstuhl -- Leibniz-Zentrum für Informatik
Pages	7:1-7:13
Number of pages	13
Volume	285
ISBN (Electronic)	9783959773058
DOIs	https://doi.org/10.4230/LIPICS.IPEC.2023.7
Publication status	Published - 2023

Publication series

Name	Leibniz International Proceedings in Informatics, LIPIcs
Volume	285
ISSN (Print)	1868-8969

Bibliographical note

Publisher Copyright:
© 2023 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. All rights reserved.

Funding

Funding Dušan Knop and Ondřej Suchý: Dušan Knop and Ondřej Suchý acknowledge the support of the Czech Science Foundation Grant No. 22-19557S. Martin Milanič: Martin Milanič acknowledges the support of the Slovenian Research and Innovation Agency (I0-0035, research program P1-0285 and research projects N1-0102, N1-0160, J1-3001, J1-3002, J1-3003, J1-4008, and J1-4084) and the research program CogniCom (0013103) at the University of Primorska. Sebastian Ordyniak: Sebastian Ordyniak acknowledges support by the Engineering and Physical Sciences Research Council (EPSRC, project EP/V00252X/1).

Funders	Funder number
Slovenian Research and Innovation Agency	N1-0160, J1-4084, J1-4008, I0-0035, J1-3001, J1-3002, N1-0102, J1-3003, 0013103
University of Primorska
Engineering and Physical Sciences Research Council	EP/V00252X/1
Grantová Agentura České Republiky	22-19557S

Keywords

NP-completeness
Treewidth
cubic graphs
degree

Access to Document

10.4230/LIPICS.IPEC.2023.7Licence: CC BY

LIPIcs.IPEC.2023.7Final published version, 928 KBLicence: CC BY

Cite this

Bodlaender, H. L., Bonnet, É., Jaffke, L., Knop, D., Lima, P. T., Milanic, M., Ordyniak, S., Pandey, S., & Suchý, O. (2023). Treewidth Is NP-Complete on Cubic Graphs. In N. Misra, & M. Wahlström (Eds.), 18th International Symposium on Parameterized and Exact Computation, IPEC 2023 (Vol. 285, pp. 7:1-7:13). Article 7 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 285). Schloss Dagstuhl -- Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPICS.IPEC.2023.7

Bodlaender, Hans L. ; Bonnet, Édouard ; Jaffke, Lars et al. / Treewidth Is NP-Complete on Cubic Graphs. 18th International Symposium on Parameterized and Exact Computation, IPEC 2023. editor / Neeldhara Misra ; Magnus Wahlström. Vol. 285 Schloss Dagstuhl -- Leibniz-Zentrum für Informatik, 2023. pp. 7:1-7:13 (Leibniz International Proceedings in Informatics, LIPIcs).

@inproceedings{d19a38367eb84e7d808af589ba70e2dc,

title = "Treewidth Is NP-Complete on Cubic Graphs",

abstract = "In this paper, we show that Treewidth is NP-complete for cubic graphs, thereby improving the result by Bodlaender and Thilikos from 1997 that Treewidth is NP-complete on graphs with maximum degree at most 9. We add a new and simpler proof of the NP-completeness of treewidth, and show that Treewidth remains NP-complete on subcubic induced subgraphs of the infinite 3-dimensional grid. ",

keywords = "NP-completeness, Treewidth, cubic graphs, degree",

author = "Bodlaender, \{Hans L.\} and {\'E}douard Bonnet and Lars Jaffke and Dusan Knop and Lima, \{Paloma T.\} and Martin Milanic and Sebastian Ordyniak and Sukanya Pandey and Ondrej Such{\'y}",

year = "2023",

doi = "10.4230/LIPICS.IPEC.2023.7",

language = "English",

volume = "285",

series = "Leibniz International Proceedings in Informatics, LIPIcs",

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

pages = "7:1--7:13",

editor = "Neeldhara Misra and Magnus Wahlstr{\"o}m",

booktitle = "18th International Symposium on Parameterized and Exact Computation, IPEC 2023",

}

Bodlaender, HL, Bonnet, É, Jaffke, L, Knop, D, Lima, PT, Milanic, M, Ordyniak, S, Pandey, S & Suchý, O 2023, Treewidth Is NP-Complete on Cubic Graphs. in N Misra & M Wahlström (eds), 18th International Symposium on Parameterized and Exact Computation, IPEC 2023. vol. 285, 7, Leibniz International Proceedings in Informatics, LIPIcs, vol. 285, Schloss Dagstuhl -- Leibniz-Zentrum für Informatik, pp. 7:1-7:13. https://doi.org/10.4230/LIPICS.IPEC.2023.7

Treewidth Is NP-Complete on Cubic Graphs. / Bodlaender, Hans L.; Bonnet, Édouard; Jaffke, Lars et al.
18th International Symposium on Parameterized and Exact Computation, IPEC 2023. ed. / Neeldhara Misra; Magnus Wahlström. Vol. 285 Schloss Dagstuhl -- Leibniz-Zentrum für Informatik, 2023. p. 7:1-7:13 7 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 285).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Treewidth Is NP-Complete on Cubic Graphs

AU - Bodlaender, Hans L.

AU - Bonnet, Édouard

AU - Jaffke, Lars

AU - Knop, Dusan

AU - Lima, Paloma T.

AU - Milanic, Martin

AU - Ordyniak, Sebastian

AU - Pandey, Sukanya

AU - Suchý, Ondrej

PY - 2023

Y1 - 2023

N2 - In this paper, we show that Treewidth is NP-complete for cubic graphs, thereby improving the result by Bodlaender and Thilikos from 1997 that Treewidth is NP-complete on graphs with maximum degree at most 9. We add a new and simpler proof of the NP-completeness of treewidth, and show that Treewidth remains NP-complete on subcubic induced subgraphs of the infinite 3-dimensional grid.

AB - In this paper, we show that Treewidth is NP-complete for cubic graphs, thereby improving the result by Bodlaender and Thilikos from 1997 that Treewidth is NP-complete on graphs with maximum degree at most 9. We add a new and simpler proof of the NP-completeness of treewidth, and show that Treewidth remains NP-complete on subcubic induced subgraphs of the infinite 3-dimensional grid.

KW - NP-completeness

KW - Treewidth

KW - cubic graphs

KW - degree

UR - https://www.scopus.com/pages/publications/85180556319

U2 - 10.4230/LIPICS.IPEC.2023.7

DO - 10.4230/LIPICS.IPEC.2023.7

M3 - Conference contribution

VL - 285

T3 - Leibniz International Proceedings in Informatics, LIPIcs

SP - 7:1-7:13

BT - 18th International Symposium on Parameterized and Exact Computation, IPEC 2023

A2 - Misra, Neeldhara

A2 - Wahlström, Magnus

PB - Schloss Dagstuhl -- Leibniz-Zentrum für Informatik

ER -

Bodlaender HL, Bonnet É, Jaffke L, Knop D, Lima PT, Milanic M et al. Treewidth Is NP-Complete on Cubic Graphs. In Misra N, Wahlström M, editors, 18th International Symposium on Parameterized and Exact Computation, IPEC 2023. Vol. 285. Schloss Dagstuhl -- Leibniz-Zentrum für Informatik. 2023. p. 7:1-7:13. 7. (Leibniz International Proceedings in Informatics, LIPIcs). doi: 10.4230/LIPICS.IPEC.2023.7

Treewidth Is NP-Complete on Cubic Graphs

Abstract

Publication series

Bibliographical note

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this