2 papers
cs.CC2023
Treewidth is NP-Complete on Cubic Graphs (and related results)
Hans L. Bodlaender, Édouard Bonnet, Lars Jaffke +6
In this paper, we give a very simple proof that Treewidth is NP-complete; this proof also shows NP-completeness on the class of co-bipartite graphs. We then improve the result by B…
cs.CC2022
XNLP-completeness for Parameterized Problems on Graphs with a Linear Structure
Hans L. Bodlaender, Carla Groenland, Hugo Jacob +2
In this paper, we showcase the class XNLP as a natural place for many hard problems parameterized by linear width measures. This strengthens existing -hardness proofs for the…