Browsing Bergen Open Research Archive by Author "Pandey, Sukanya"
Now showing items 1-1 of 1
-
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, 2023)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 ...