تقرير
Treewidth Inapproximability and Tight ETH Lower Bound
العنوان: | Treewidth Inapproximability and Tight ETH Lower Bound |
---|---|
المؤلفون: | Bonnet, Édouard |
سنة النشر: | 2024 |
المجموعة: | Computer Science Mathematics |
مصطلحات موضوعية: | Computer Science - Computational Complexity, Computer Science - Discrete Mathematics, Computer Science - Data Structures and Algorithms, Mathematics - Combinatorics, 68Q17, F.2.2 |
الوصف: | 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)}}$. Comment: 10 pages, 1 figure |
نوع الوثيقة: | Working Paper |
URL الوصول: | http://arxiv.org/abs/2406.11628 |
رقم الأكسشن: | edsarx.2406.11628 |
قاعدة البيانات: | arXiv |
كن أول من يترك تعليقا!