Treewidth is NP-Complete on Cubic Graphs
Hans Bodlaender, Édouard Bonnet, Lars Jaffke, Dušan Knop, Paloma Lima, Martin Milanič, Sebastian Ordyniak, Sukanya Pandey, Ondřej Suchý
Source 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, and on cubic line graphs.
Evidence graph
No public relationships recorded yet.
Integrity note: This page is a factual metadata record created by deterministic ingestion. It is not a claim that the work moves a mathematical frontier or has been independently verified.