Treewidth Inapproximability and Tight ETH Lower Bound

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^{\hat{I}\text{c◯}(n)}$ time, unless the Exponential-Time Hypothesis fails. We further derive, under the latter assumption, that there are some constants $\hat{I}´>1$ and $c>0$ such that $\hat{I}´$-approximating Treewidth requires time $2^{\hat{I}\text{c◯}(n/{\log }^{c}n)}$.

11 pages, 1 figure