Treewidth Inapproximability and Tight ETH Lower Bound
<|reference_start|>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^{\Omega(n)}$ time, unless the Exponential-Time Hypothesis fails. We further derive, under the latter assumption, that there is some constant $\delta > 1$ such that $\delta$-approximating Treewidth requires time $2^{n^{1-o(1)}}$.<|reference_end|>
@article{bonnet2024treewidth,
    title={Treewidth Inapproximability and Tight ETH Lower Bound},
    author={'Edouard Bonnet},
    journal={arXiv preprint arXiv:2406.11628},
    year={2024},
    archivePrefix={arXiv},
    eprint={2406.11628},
    primaryClass={cs.CC cs.DM cs.DS math.CO}
}