Treewidth is NP-Complete on Cubic Graphs

  • Hans L. Bodlaender
  • Édouard Bonnet
  • Lars Jaffke
  • Dušan Knop
  • Paloma T. Lima
  • Martin Milanič
  • Sebastian Ordyniak
  • Sukanya Pandey
  • Ondřej Suchý
DOI: https://doi.org/10.37236/13205

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.

Published
2025-08-22
Issue
Volume 32, Issue 3 (2025)
Article Number
P3.36