Polynomial-Time Approximation of Independent Set Parameterized by Treewidth

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

*Tämän työn vastaava kirjoittaja

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussaConference article in proceedingsScientificvertaisarvioitu

17 Lataukset (Pure)

Abstrakti

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.

AlkuperäiskieliEnglanti
Otsikko31st Annual European Symposium on Algorithms, ESA 2023
ToimittajatInge Li Gortz, Martin Farach-Colton, Simon J. Puglisi, Grzegorz Herman
KustantajaSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Sivut1-13
Sivumäärä13
ISBN (elektroninen)978-3-95977-295-2
DOI - pysyväislinkit
TilaJulkaistu - syysk. 2023
OKM-julkaisutyyppiA4 Artikkeli konferenssijulkaisussa
TapahtumaEuropean Symposium on Algorithms - Amsterdam, Alankomaat
Kesto: 4 syysk. 20236 syysk. 2023
Konferenssinumero: 31

Julkaisusarja

NimiLeibniz International Proceedings in Informatics, LIPIcs
KustantajaSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Vuosikerta274
ISSN (elektroninen)1868-8969

Conference

ConferenceEuropean Symposium on Algorithms
LyhennettäESA
Maa/AlueAlankomaat
KaupunkiAmsterdam
Ajanjakso04/09/202306/09/2023

Sormenjälki

Sukella tutkimusaiheisiin 'Polynomial-Time Approximation of Independent Set Parameterized by Treewidth'. Ne muodostavat yhdessä ainutlaatuisen sormenjäljen.

Siteeraa tätä