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:10.37236/13205

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ý

Sub Algorithms and Complexity

Research output: Contribution to journal › Article › Academic › peer-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 Tree-width 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.

Original language	English
Article number	P3.36
Number of pages	23
Journal	Electronic Journal of Combinatorics
Volume	32
Issue number	3
DOIs	https://doi.org/10.37236/13205
Publication status	Published - 22 Aug 2025

Bibliographical note

Publisher Copyright:
© The authors.

Access to Document

10.37236/13205Licence: CC BY-ND

Treewidth is NP-Complete on Cubic GraphsFinal published version, 551 KBLicence: CC BY-ND

Cite this

@article{b8b989db23e34f5e846aad1b8182829e,

title = "Treewidth is NP-Complete on Cubic Graphs",

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 Tree-width 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.",

author = "Bodlaender, \{Hans L.\} and {\'E}douard Bonnet and Lars Jaffke and Du{\v s}an Knop and Lima, \{Paloma T.\} and Martin Milani{\v c} and Sebastian Ordyniak and Sukanya Pandey and Ond{\v r}ej Such{\'y}",

note = "Publisher Copyright: {\textcopyright} The authors.",

year = "2025",

month = aug,

day = "22",

doi = "10.37236/13205",

language = "English",

volume = "32",

journal = "Electronic Journal of Combinatorics",

issn = "1077-8926",

publisher = "Electronic Journal of Combinatorics",

number = "3",

}

TY - JOUR

T1 - Treewidth is NP-Complete on Cubic Graphs

AU - Bodlaender, Hans L.

AU - Bonnet, Édouard

AU - Jaffke, Lars

AU - Knop, Dušan

AU - Lima, Paloma T.

AU - Milanič, Martin

AU - Ordyniak, Sebastian

AU - Pandey, Sukanya

AU - Suchý, Ondřej

PY - 2025/8/22

Y1 - 2025/8/22

N2 - In this paper, we show that Treewidth is NP-complete for cubic graphs, thereby improving the result by Bodlaender and Thilikos from 1997 that Tree-width 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.

AB - In this paper, we show that Treewidth is NP-complete for cubic graphs, thereby improving the result by Bodlaender and Thilikos from 1997 that Tree-width 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.

UR - https://www.scopus.com/pages/publications/105014647862

U2 - 10.37236/13205

DO - 10.37236/13205

M3 - Article

AN - SCOPUS:105014647862

SN - 1077-8926

VL - 32

JO - Electronic Journal of Combinatorics

JF - Electronic Journal of Combinatorics

IS - 3

M1 - P3.36

ER -

Treewidth is NP-Complete on Cubic Graphs

Abstract

Bibliographical note

Access to Document

Other files and links

Fingerprint

Cite this