2026-07-23T22:21:30Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19426 2024-03-06T11:04:01Z ddc:004 open_access

Treewidth Is NP-Complete on Cubic Graphs Bodlaender, Hans L. Bonnet, Édouard Jaffke, Lars Knop, Dušan Lima, Paloma T. Milanič, Martin Ordyniak, Sebastian Pandey, Sukanya Suchý, Ondřej Treewidth cubic graphs degree NP-completeness 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Hans L. Bodlaender and Édouard Bonnet and Lars Jaffke and Dušan Knop and Paloma T. Lima and Martin Milanič and Sebastian Ordyniak and Sukanya Pandey and Ondřej Suchý 2023 Is Part Of LIPIcs, Volume 285, 18th International Symposium on Parameterized and Exact Computation (IPEC 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2023.7 urn:nbn:de:0030-drops-194263 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.7 eng https://creativecommons.org/licenses/by/4.0/legalcode