Geodesic
Treewidth is NP-complete on cubic graphs
Hans Bodlaender1 ; Édouard Bonnet2 ; Lars Jaffke3 ; Dušan Knop4 ; Paloma Lima5 ; Martin Milanič6 ; Sebastian Ordyniak7 ; Sukanya Pandey1 ; Ondřej Suchý4
1Utrecht University
2LIP, ENS Lyon
3University of Bergen
4Czech Technical University in Prague
5IT University of Copenhagen
6FAMNIT and IAM, University of Primorska, Koper
7University of Leeds
The electronic journal of combinatorics, Tome 32 (2025) no. 3
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

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.
DOI : 10.37236/13205
Classification : 68R10, 05C05, 68Q17

Hans Bodlaender  1   ; Édouard Bonnet  2   ; Lars Jaffke  3   ; Dušan Knop  4   ; Paloma Lima  5   ; Martin Milanič  6   ; Sebastian Ordyniak  7   ; Sukanya Pandey  1   ; Ondřej Suchý  4

1 Utrecht University
2 LIP, ENS Lyon
3 University of Bergen
4 Czech Technical University in Prague
5 IT University of Copenhagen
6 FAMNIT and IAM, University of Primorska, Koper
7 University of Leeds 
@article{10_37236_13205,
     author = {Hans Bodlaender and \'Edouard Bonnet and Lars Jaffke and Du\v{s}an Knop and Paloma Lima and Martin Milani\v{c} and Sebastian Ordyniak and Sukanya Pandey and Ond\v{r}ej Such\'y},
     title = {Treewidth is {NP-complete} on cubic graphs},
     journal = {The electronic journal of combinatorics},
     year = {2025},
     volume = {32},
     number = {3},
     doi = {10.37236/13205},
     zbl = {8097664},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/13205/}
}
TY  - JOUR
AU  - Hans Bodlaender
AU  - Édouard Bonnet
AU  - Lars Jaffke
AU  - Dušan Knop
AU  - Paloma Lima
AU  - Martin Milanič
AU  - Sebastian Ordyniak
AU  - Sukanya Pandey
AU  - Ondřej Suchý
TI  - Treewidth is NP-complete on cubic graphs
JO  - The electronic journal of combinatorics
PY  - 2025
VL  - 32
IS  - 3
UR  - http://geodesic.mathdoc.fr/articles/10.37236/13205/
DO  - 10.37236/13205
ID  - 10_37236_13205
ER  - 
%0 Journal Article
%A Hans Bodlaender
%A Édouard Bonnet
%A Lars Jaffke
%A Dušan Knop
%A Paloma Lima
%A Martin Milanič
%A Sebastian Ordyniak
%A Sukanya Pandey
%A Ondřej Suchý
%T Treewidth is NP-complete on cubic graphs
%J The electronic journal of combinatorics
%D 2025
%V 32
%N 3
%U http://geodesic.mathdoc.fr/articles/10.37236/13205/
%R 10.37236/13205
%F 10_37236_13205
Hans Bodlaender; Édouard Bonnet; Lars Jaffke; Dušan Knop; Paloma Lima; Martin Milanič; Sebastian Ordyniak; Sukanya Pandey; Ondřej Suchý. Treewidth is NP-complete on cubic graphs. The electronic journal of combinatorics, Tome 32 (2025) no. 3. doi: 10.37236/13205

Cité par Sources :