Projects per year
Abstract
We prove the following result about approximating the maximum independent set in a graph. Informally, we show that any approximation algorithm with a “nontrivial” 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 stateoftheart O(n · (log log n)^{2} / log^{3} n)approximation algorithm by Feige (2004), this implies an O(tw · (log log tw)^{3} / log^{3} tw)approximation algorithm.
Original language  English 

Title of host publication  31st Annual European Symposium on Algorithms, ESA 2023 
Editors  Inge Li Gortz, Martin FarachColton, Simon J. Puglisi, Grzegorz Herman 
Publisher  Schloss Dagstuhl  LeibnizZentrum für Informatik 
Pages  113 
Number of pages  13 
ISBN (Electronic)  9783959772952 
DOIs  
Publication status  Published  Sept 2023 
MoE publication type  A4 Conference publication 
Event  European Symposium on Algorithms  Amsterdam, Netherlands Duration: 4 Sept 2023 → 6 Sept 2023 Conference number: 31 
Publication series
Name  Leibniz International Proceedings in Informatics, LIPIcs 

Publisher  Schloss Dagstuhl  LeibnizZentrum für Informatik 
Volume  274 
ISSN (Electronic)  18688969 
Conference
Conference  European Symposium on Algorithms 

Abbreviated title  ESA 
Country/Territory  Netherlands 
City  Amsterdam 
Period  04/09/2023 → 06/09/2023 
Keywords
 Approximation Algorithms
 Maximum Independent Set
 Parameterized Approximation
 Treewidth
Fingerprint
Dive into the research topics of 'PolynomialTime Approximation of Independent Set Parameterized by Treewidth'. Together they form a unique fingerprint.Projects
 1 Finished

ALGOCom: Novel Algorithmic Techniques through the Lens of Combinatorics
Chalermsook, P., Jindal, G., Franck, M., Jiamjitrak, W., Khodamoradi, K., Yingchareonthawornchai, S., Gadekar, A., Orgo, L. & Spoerhase, J.
01/02/2018 → 31/01/2024
Project: EU: ERC grants