Treewidth Inapproximability and Tight ETH Lower Bound

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