|国家预印本平台
首页|Treewidth Inapproximability and Tight ETH Lower Bound

Treewidth Inapproximability and Tight ETH Lower Bound

Treewidth Inapproximability and Tight ETH Lower Bound

来源:Arxiv_logoArxiv
英文摘要

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 are some constants $δ> 1$ and $c>0$ such that $δ$-approximating Treewidth requires time $2^{Ω(n/\log^c n)}$.

Édouard Bonnet

计算技术、计算机技术

Édouard Bonnet.Treewidth Inapproximability and Tight ETH Lower Bound[EB/OL].(2025-06-23)[2025-08-02].https://arxiv.org/abs/2406.11628.点此复制

评论