تقرير
Polynomial-time Approximation of Independent Set Parameterized by Treewidth
العنوان: | Polynomial-time Approximation of Independent Set Parameterized by Treewidth |
---|---|
المؤلفون: | Chalermsook, Parinya, Fomin, Fedor, Hamm, Thekla, Korhonen, Tuukka, Nederlof, Jesper, Orgo, Ly |
سنة النشر: | 2023 |
المجموعة: | Computer Science |
مصطلحات موضوعية: | Computer Science - Data Structures and Algorithms |
الوصف: | We prove the following result about approximating the maximum independent set in a graph. Informally, we show that any approximation algorithm with a ``non-trivial'' approximation ratio (as a function of the number of vertices of the input graph $G$) can be turned into an approximation algorithm achieving almost the same ratio, albeit as a function of the treewidth of $G$. More formally, we prove that for any function $f$, the existence of a polynomial time $(n/f(n))$-approximation algorithm yields the existence of a polynomial time $O(tw \cdot\log{f(tw)}/f(tw))$-approximation algorithm, where $n$ and $tw$ denote the number of vertices and the width of a given tree decomposition of the input graph. By pipelining our result with the state-of-the-art $O(n \cdot (\log \log n)^2/\log^3 n)$-approximation algorithm by Feige (2004), this implies an $O(tw \cdot (\log \log tw)^3/\log^3 tw)$-approximation algorithm. Comment: To appear in the 31st Annual European Symposium on Algorithms (ESA 2023) |
نوع الوثيقة: | Working Paper |
URL الوصول: | http://arxiv.org/abs/2307.01341 |
رقم الأكسشن: | edsarx.2307.01341 |
قاعدة البيانات: | arXiv |
الوصف غير متاح. |