TY - GEN

T1 - Polynomial-Time Approximation of Independent Set Parameterized by Treewidth

AU - Chalermsook, Parinya

AU - Fomin, Fedor V.

AU - Hamm, Thekla

AU - Korhonen, Tuukka

AU - Nederlof, Jesper

AU - Orgo, Ly

N1 - 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).
Publisher Copyright:
© Parinya Chalermsook, Fedor Fomin, Thekla Hamm, Tuukka Korhonen, Jesper Nederlof, and Ly Orgo.

PY - 2023/9

Y1 - 2023/9

N2 - 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.

AB - 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.

KW - Maximum Independent Set

KW - Treewidth

KW - Approximation Algorithms

KW - Parameterized Approximation

UR - http://www.scopus.com/inward/record.url?scp=85173537796&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.ESA.2023.33

DO - 10.4230/LIPIcs.ESA.2023.33

M3 - Conference contribution

VL - 274

T3 - Leibniz International Proceedings in Informatics, LIPIcs

SP - 33:1-33:13

BT - 31st Annual European Symposium on Algorithms, ESA 2023, September 4-6, 2023, Amsterdam, The Netherlands

A2 - Gørtz, Inge Li

A2 - Farach-Colton, Martin

A2 - Puglisi, Simon J.

A2 - Herman, Grzegorz

PB - Schloss Dagstuhl – Leibniz-Zentrum für Informatik GmbH

ER -