2 papers
cs.CC2025
Treedepth Inapproximability and Exponential ETH Lower Bound
Ãdouard Bonnet, Daniel Neuen, Marek SokoÅowski
Treedepth is a central parameter to algorithmic graph theory. The current state-of-the-art in computing and approximating treedepth consists of a -time exact algorith…
cs.CC2025
Treewidth Inapproximability and Tight ETH Lower Bound
Ãdouard Bonnet
We present a simple, self-contained, linear reduction from 3-SAT to Treewidth. Specifically, it shows that 1.00005-approximating Treewidth is NP-hard, and solving Treewidth exactly…