Polynomial-Time Approximation of Independent Set Parameterized by Treewidth

Parinya Chalermsook; Fedor V. Fomin; Thekla Hamm; Tuukka Korhonen; Jesper Nederlof; Ly Orgo

doi:10.4230/LIPIcs.ESA.2023.33

Polynomial-Time Approximation of Independent Set Parameterized by Treewidth

Parinya Chalermsook
, Fedor V. Fomin
, Thekla Hamm
, Tuukka Korhonen
, Jesper Nederlof
, Ly Orgo

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

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)² / log³ n)-approximation algorithm by Feige (2004), this implies an O(tw · (log log tw)³ / log³ tw)-approximation algorithm.

Original language	English
Title of host publication	31st Annual European Symposium on Algorithms, ESA 2023, September 4-6, 2023, Amsterdam, The Netherlands
Editors	Inge Li Gørtz, Martin Farach-Colton, Simon J. Puglisi, Grzegorz Herman
Publisher	Schloss Dagstuhl – Leibniz-Zentrum für Informatik GmbH
Pages	33:1-33:13
Volume	274
ISBN (Electronic)	9783959772952
DOIs	https://doi.org/10.4230/LIPIcs.ESA.2023.33
Publication status	Published - Sept 2023

Publication series

Name	Leibniz International Proceedings in Informatics, LIPIcs
Volume	274
ISSN (Print)	1868-8969

Bibliographical note

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.

Keywords

Maximum Independent Set
Treewidth
Approximation Algorithms
Parameterized Approximation

Access to Document

10.4230/LIPIcs.ESA.2023.33Licence: CC BY

LIPIcs-ESA-2023-33Final published version, 678 KBLicence: CC BY

Cite this

Chalermsook, P., Fomin, F. V., Hamm, T., Korhonen, T., Nederlof, J., & Orgo, L. (2023). Polynomial-Time Approximation of Independent Set Parameterized by Treewidth. In I. L. Gørtz, M. Farach-Colton, S. J. Puglisi, & G. Herman (Eds.), 31st Annual European Symposium on Algorithms, ESA 2023, September 4-6, 2023, Amsterdam, The Netherlands (Vol. 274, pp. 33:1-33:13). Article 33 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 274). Schloss Dagstuhl – Leibniz-Zentrum für Informatik GmbH. https://doi.org/10.4230/LIPIcs.ESA.2023.33

Chalermsook, Parinya ; Fomin, Fedor V. ; Hamm, Thekla et al. / Polynomial-Time Approximation of Independent Set Parameterized by Treewidth. 31st Annual European Symposium on Algorithms, ESA 2023, September 4-6, 2023, Amsterdam, The Netherlands. editor / Inge Li Gørtz ; Martin Farach-Colton ; Simon J. Puglisi ; Grzegorz Herman. Vol. 274 Schloss Dagstuhl – Leibniz-Zentrum für Informatik GmbH, 2023. pp. 33:1-33:13 (Leibniz International Proceedings in Informatics, LIPIcs).

@inproceedings{59811ade7e9d43fba78c263c3a76dd2f,

title = "Polynomial-Time Approximation of Independent Set Parameterized by Treewidth",

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.",

keywords = "Maximum Independent Set, Treewidth, Approximation Algorithms, Parameterized Approximation",

author = "Parinya Chalermsook and Fomin, \{Fedor V.\} and Thekla Hamm and Tuukka Korhonen and Jesper Nederlof and Ly Orgo",

note = "Funding Information: Funding Parinya Chalermsook: Supported by European Research Council (ERC) under the European Union{\textquoteright}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{\textquoteright}s Horizon 2020 research and innovation programme (grant agreement No 853234). Ly Orgo: Supported by European Research Council (ERC) under the European Union{\textquoteright}s Horizon 2020 research and innovation programme (grant agreement No 759557). Publisher Copyright: {\textcopyright} Parinya Chalermsook, Fedor Fomin, Thekla Hamm, Tuukka Korhonen, Jesper Nederlof, and Ly Orgo.",

year = "2023",

month = sep,

doi = "10.4230/LIPIcs.ESA.2023.33",

language = "English",

volume = "274",

series = "Leibniz International Proceedings in Informatics, LIPIcs",

publisher = "Schloss Dagstuhl – Leibniz-Zentrum f{\"u}r Informatik GmbH",

pages = "33:1--33:13",

editor = "G{\o}rtz, \{Inge Li\} and Martin Farach-Colton and Puglisi, \{Simon J.\} and Grzegorz Herman",

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

}

Chalermsook, P, Fomin, FV, Hamm, T, Korhonen, T, Nederlof, J & Orgo, L 2023, Polynomial-Time Approximation of Independent Set Parameterized by Treewidth. in IL Gørtz, M Farach-Colton, SJ Puglisi & G Herman (eds), 31st Annual European Symposium on Algorithms, ESA 2023, September 4-6, 2023, Amsterdam, The Netherlands. vol. 274, 33, Leibniz International Proceedings in Informatics, LIPIcs, vol. 274, Schloss Dagstuhl – Leibniz-Zentrum für Informatik GmbH, pp. 33:1-33:13. https://doi.org/10.4230/LIPIcs.ESA.2023.33

Polynomial-Time Approximation of Independent Set Parameterized by Treewidth. / Chalermsook, Parinya; Fomin, Fedor V.; Hamm, Thekla et al.
31st Annual European Symposium on Algorithms, ESA 2023, September 4-6, 2023, Amsterdam, The Netherlands. ed. / Inge Li Gørtz; Martin Farach-Colton; Simon J. Puglisi; Grzegorz Herman. Vol. 274 Schloss Dagstuhl – Leibniz-Zentrum für Informatik GmbH, 2023. p. 33:1-33:13 33 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 274).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

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 - https://www.scopus.com/pages/publications/85173537796

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 -

Chalermsook P, Fomin FV, Hamm T, Korhonen T, Nederlof J, Orgo L. Polynomial-Time Approximation of Independent Set Parameterized by Treewidth. In Gørtz IL, Farach-Colton M, Puglisi SJ, Herman G, editors, 31st Annual European Symposium on Algorithms, ESA 2023, September 4-6, 2023, Amsterdam, The Netherlands. Vol. 274. Schloss Dagstuhl – Leibniz-Zentrum für Informatik GmbH. 2023. p. 33:1-33:13. 33. (Leibniz International Proceedings in Informatics, LIPIcs). doi: 10.4230/LIPIcs.ESA.2023.33

Polynomial-Time Approximation of Independent Set Parameterized by Treewidth

Abstract

Publication series

Bibliographical note

Keywords

Access to Document

Other files and links

Fingerprint

Cite this