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Ω(n) time, unless the Exponential-Time Hypothesis fails. We further derive, under the latter assumption, that there is some constant δ > 1 such that δ-approximating Treewidth requires time 2^n¹⁻ᵒ⁽¹⁾.