Treewidth is NP-Complete on Cubic Graphs (and related results)

January 24, 2023 ยท The Ethereal ยท ๐Ÿ› arXiv.org

๐Ÿ”ฎ THE ETHEREAL: The Ethereal
Pure theory โ€” exists on a plane beyond code

"No code URL or promise found in abstract"

Evidence collected by the PWNC Scanner

Authors Hans L. Bodlaender, ร‰douard Bonnet, Lars Jaffke, Duลกan Knop, Paloma T. Lima, Martin Milaniฤ, Sebastian Ordyniak, Sukanya Pandey, Ondล™ej Suchรฝ arXiv ID 2301.10031 Category cs.CC: Computational Complexity Cross-listed cs.DS, math.CO Citations 0 Venue arXiv.org Last Checked 3 months ago
Abstract
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 Bodlaender and Thilikos from 1997 that Treewidth is NP-complete on graphs with maximum degree at most 9, by showing that Treewidth is NP-complete on cubic graphs.
Community shame:
Not yet rated
๐Ÿ“„ View on arXiv ๐ŸŒ View on ar5iv ๐Ÿ“‘ PDF ๐ŸŽ‰ Report Code Found
Community Contributions

Found the code? Know the venue? Think something is wrong? Let us know!

๐Ÿ“œ Similar Papers

In the same crypt โ€” Computational Complexity