Polynomial-Time Approximation of Independent Set Parameterized by Treewidth

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

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference article in proceedingsScientificpeer-review

7 Downloads (Pure)

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.

Original languageEnglish
Title of host publication31st Annual European Symposium on Algorithms, ESA 2023
EditorsInge Li Gortz, Martin Farach-Colton, Simon J. Puglisi, Grzegorz Herman
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Pages1-13
Number of pages13
ISBN (Electronic)978-3-95977-295-2
DOIs
Publication statusPublished - Sept 2023
MoE publication typeA4 Conference publication
EventEuropean Symposium on Algorithms - Amsterdam, Netherlands
Duration: 4 Sept 20236 Sept 2023
Conference number: 31

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Volume274
ISSN (Electronic)1868-8969

Conference

ConferenceEuropean Symposium on Algorithms
Abbreviated titleESA
Country/TerritoryNetherlands
CityAmsterdam
Period04/09/202306/09/2023

Keywords

  • Approximation Algorithms
  • Maximum Independent Set
  • Parameterized Approximation
  • Treewidth

Fingerprint

Dive into the research topics of 'Polynomial-Time Approximation of Independent Set Parameterized by Treewidth'. Together they form a unique fingerprint.

Cite this