What type of study is this?

This is a Literature Review study.

August 21, 2025Open Access

Treewidth is NP-Complete on Cubic Graphs

Key Points

Treewidth is proven to be NP-complete for cubic graphs, reinforcing its complexity.
The result improves an earlier finding by showing NP-completeness on cubic line graphs and subcubic subgraphs.
This research utilizes a new proof method for establishing treewidth's NP-completeness in relevant graphs.
Implications extend to the study of induced subgraphs within the infinite 3-dimensional grid.

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.

Treewidth is NP-Complete on Cubic Graphs

Key Points

Abstract

Cite This Study

Also Consider

Also Consider