Back to Search
Start Over
Treewidth Inapproximability and Tight ETH Lower Bound
- Publication Year :
- 2024
-
Abstract
- 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 requires $2^{\Omega(n)}$ time, unless the Exponential-Time Hypothesis fails. We further derive, under the latter assumption, that there is some constant $\delta > 1$ such that $\delta$-approximating Treewidth requires time $2^{n^{1-o(1)}}$.<br />Comment: 10 pages, 1 figure
Details
- Database :
- arXiv
- Publication Type :
- Report
- Accession number :
- edsarx.2406.11628
- Document Type :
- Working Paper