Treewidth is NP-Complete on Cubic Graphs

Bodlaender, Hans L.; Bonnet, Édouard; Jaffke, Lars; Knop, Dusan; Lima, Paloma Thome de; Milanič, Martin; Ordyniak, Sebastian; Pandey, Sukanya; Suchy, Ondrey
Journal article, Peer reviewed
Published version
Thumbnail
View/Open
URI
https://hdl.handle.net/11250/3122315
Date
2023
Metadata
Show full item record
Collections
Original version
Leibniz International Proceedings in Informatics. 2023, 285, 7:1-7:13.   10.4230/LIPIcs.IPEC.2023.7
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.
Publisher
Dagstuhl Publishing
Journal
Leibniz International Proceedings in Informatics
Copyright
Copyright 2023 The Autors(s)
Navngivelse 4.0 Internasjonal
Except where otherwise noted, this item's license is described as Navngivelse 4.0 Internasjonal