License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2023.33
URN: urn:nbn:de:0030-drops-186865
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18686/
Go to the corresponding LIPIcs Volume Portal

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

Polynomial-Time Approximation of Independent Set Parameterized by Treewidth

pdf-format:
LIPIcs-ESA-2023-33.pdf (0.7 MB)

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.

BibTeX - Entry

@InProceedings{chalermsook_et_al:LIPIcs.ESA.2023.33,
  author =	{Chalermsook, Parinya and Fomin, Fedor and Hamm, Thekla and Korhonen, Tuukka and Nederlof, Jesper and Orgo, Ly},
  title =	{{Polynomial-Time Approximation of Independent Set Parameterized by Treewidth}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{33:1--33:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-295-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{274},
  editor =	{G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/18686},
  URN =		{urn:nbn:de:0030-drops-186865},
  doi =		{10.4230/LIPIcs.ESA.2023.33},
  annote =	{Keywords: Maximum Independent Set, Treewidth, Approximation Algorithms, Parameterized Approximation}
}

Keywords: Maximum Independent Set, Treewidth, Approximation Algorithms, Parameterized Approximation
Collection: 31st Annual European Symposium on Algorithms (ESA 2023)
Issue Date: 2023
Date of publication: 30.08.2023

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI