تقرير
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 |
كن أول من يترك تعليقا!