Treewidth Inapproximability and Tight ETH Lower Bound
Édouard Bonnet · Journal of the ACM · 2025
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(\sqrt {\log \text{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^{\Omega (\sqrt 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^{\Omega (n/\log ^c n)} \) .