Treewidth Inapproximability and Tight ETH Lower Bound

Despite the algorithmic importance of treewidth, both its complexity and approximability present large knowledge gaps. While the best currently known polynomial-time approximation algorithm has ratio O( √ log OPT), no approximation factor could be ruled out under P ̸ = NP alone. There are 2 O(n) -time algorithms to compute the treewidth of n-vertex graphs, but the Exponential-Time Hypothesis (ETH) was only known to imply that 2 Ω( √ n) time is required. The reason is that all the known hardness constructions use Cutwidth or Pathwidth on bounded-degree graphs as an intermediate step in a long chain of reductions, for which neither inapproximability nor sharp ETH lower bound is known. We present a simple, self-contained reduction from 3-SAT to Treewidth. Our reduction partially closes the first gap and fully resolves the second. Namely, we show that 1.00005-approximating Treewidth is NP-hard, and solving Treewidth exactly requires 2 Ω(n) time, unless the ETH fails. We further derive, under the latter assumption, that there are some constants δ > 1 and c > 0 such that δ-approximating Treewidth requires time 2 Ω(n/ log c n) .