Treewidth is NP-Complete on Cubic Graphs
Publication date
2025-08-22
Authors
Bodlaender, Hans L.
Bonnet, Édouard
Jaffke, Lars
Knop, Dušan
Lima, Paloma T.
Milanič, Martin
Ordyniak, Sebastian
Pandey, Sukanya
Suchý, Ondřej
Editors
Advisors
Supervisors
Document Type
Article
Metadata
Show full item recordCollections
License
cc_by_nd
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 Tree-width 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, and on cubic line graphs.
Keywords
Theoretical Computer Science, Geometry and Topology, Discrete Mathematics and Combinatorics, Computational Theory and Mathematics, Applied Mathematics
Citation
Bodlaender, H L, Bonnet, É, Jaffke, L, Knop, D, Lima, P T, Milanič, M, Ordyniak, S, Pandey, S & Suchý, O 2025, 'Treewidth is NP-Complete on Cubic Graphs', Electronic Journal of Combinatorics, vol. 32, no. 3, P3.36. https://doi.org/10.37236/13205