Polynomial-Time Approximation of Independent Set Parameterized by Treewidth
Loading...
Access rights
openAccess
publishedVersion
URL
Journal Title
Journal ISSN
Volume Title
A4 Artikkeli konferenssijulkaisussa
This publication is imported from Aalto University research portal.
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Other link related to publication (opens in new window)
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Other link related to publication (opens in new window)
Date
Department
Major/Subject
Mcode
Degree programme
Language
en
Pages
13
Series
31st Annual European Symposium on Algorithms, ESA 2023, pp. 1-13, Leibniz International Proceedings in Informatics, LIPIcs ; Volume 274
Abstract
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 · 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 · (log log n)2 / log3 n)-approximation algorithm by Feige (2004), this implies an O(tw · (log log tw)3 / log3 tw)-approximation algorithm.Description
Funding Information: Funding Parinya Chalermsook: Supported by European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 759557). Fedor Fomin: Supported by the Research Council of Norway via the project BWCA (grant no. 314528). Thekla Hamm: Supported by the Austrian Science Fund (FWF, project J4651-N). Tuukka Korhonen: Supported by the Research Council of Norway via the project BWCA (grant no. 314528). Jesper Nederlof : Supported by the project CRACKNP that has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 853234). Ly Orgo: Supported by European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 759557). | openaire: EC/H2020/759557/EU//ALGOCom
Other note
Citation
Chalermsook, P, Fomin, F, Hamm, T, Korhonen, T, Nederlof, J & Orgo, L 2023, Polynomial-Time Approximation of Independent Set Parameterized by Treewidth. in I Li Gortz, M Farach-Colton, S J Puglisi & G Herman (eds), 31st Annual European Symposium on Algorithms, ESA 2023., 33, Leibniz International Proceedings in Informatics, LIPIcs, vol. 274, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, pp. 1-13, European Symposium on Algorithms, Amsterdam, Netherlands, 04/09/2023. https://doi.org/10.4230/LIPIcs.ESA.2023.33