Treewidth Is NP-Complete on Cubic Graphs

Hans L. Bodlaender, Édouard Bonnet, Lars Jaffke, Dusan Knop, Paloma T. Lima, Martin Milanic, Sebastian Ordyniak, Sukanya Pandey, Ondrej Suchý

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

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.
Original languageEnglish
Title of host publication18th International Symposium on Parameterized and Exact Computation, IPEC 2023
EditorsNeeldhara Misra, Magnus Wahlström
PublisherSchloss Dagstuhl -- Leibniz-Zentrum für Informatik
Pages7:1-7:13
Number of pages13
Volume285
ISBN (Electronic)9783959773058
DOIs
Publication statusPublished - 2023

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume285
ISSN (Print)1868-8969

Keywords

  • NP-completeness
  • Treewidth
  • cubic graphs
  • degree

Fingerprint

Dive into the research topics of 'Treewidth Is NP-Complete on Cubic Graphs'. Together they form a unique fingerprint.

Cite this