Treewidth Is NP-Complete on Cubic Graphs
Publication date
2023
Authors
Bodlaender, Hans
Bonnet, Édouard
Jaffke, Lars
Knop, Dusan
Lima, Paloma T.
Milanic, Martin
Ordyniak, Sebastian
Pandey, Sukanya
Suchý, Ondrej
Editors
Misra, Neeldhara
Wahlström, Magnus
Advisors
Supervisors
Document Type
Part of book
Metadata
Show full item recordCollections
License
cc_by
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, Software
Citation
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, 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