Document Open Access Logo

Polynomial-Time Approximation of Independent Set Parameterized by Treewidth

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

PDF

File

Thumbnail PDF
PDF
LIPIcs.ESA.2023.33.pdf
  • Filesize: 0.66 MB
  • 13 pages

Document Identifiers

Subject Classification

ACM Subject Classification
  • Theory of computation → Approximation algorithms analysis
  • Theory of computation → Graph algorithms analysis
Keywords
  • Maximum Independent Set
  • Treewidth
  • Approximation Algorithms
  • Parameterized Approximation

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

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.

Cite As Get BibTex

Parinya Chalermsook, Fedor Fomin, Thekla Hamm, Tuukka Korhonen, Jesper Nederlof, and Ly Orgo. Polynomial-Time Approximation of Independent Set Parameterized by Treewidth. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 33:1-33:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.ESA.2023.33

Author Details

Parinya Chalermsook
  • Aalto University, Finland
Fedor Fomin
  • University of Bergen, Norway
Thekla Hamm
  • Utrecht University, The Netherlands
Tuukka Korhonen
  • University of Bergen, Norway
Jesper Nederlof
  • Utrecht University, The Netherlands
Ly Orgo
  • Aalto University, Finland

Funding

  • Chalermsook, Parinya: Supported by European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 759557).
  • Fomin, Fedor: Supported by the Research Council of Norway via the project BWCA (grant no. 314528).
  • Hamm, Thekla: Supported by the Austrian Science Fund (FWF, project J4651-N).
  • Korhonen, Tuukka: Supported by the Research Council of Norway via the project BWCA (grant no. 314528).
  • Nederlof, Jesper: 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).
  • Orgo, Ly: Supported by European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 759557).

Acknowledgements

The research presented in this paper was initiated partially during the trimester on Discrete Optimization at Hausdorff Research Institute for Mathematics (HIM) in Bonn, Germany.

References

  1. Noga Alon and Nabil Kahalé. Approximating the independence number via the theta-function. Math. Program., 80:253-264, 1998. URL: https://doi.org/10.1007/BF01581168.
  2. Per Austrin, Subhash Khot, and Muli Safra. Inapproximability of vertex cover and independent set in bounded degree graphs. Theory Comput., 7(1):27-43, 2011. URL: https://doi.org/10.4086/toc.2011.v007a003.
  3. Nikhil Bansal, Parinya Chalermsook, Bundit Laekhanukit, Danupon Nanongkai, and Jesper Nederlof. New tools and connections for exponential-time approximation. Algorithmica, 81:3993-4009, 2019. Google Scholar
  4. Nikhil Bansal, Anupam Gupta, and Guru Guruganesh. On the lovász theta function for independent sets in sparse graphs. SIAM J. Comput., 47(3):1039-1055, 2018. URL: https://doi.org/10.1137/15M1051002.
  5. Hans L. Bodlaender and Torben Hagerup. Parallel algorithms with optimal speedup for bounded treewidth. SIAM J. Comput., 27(6):1725-1746, 1998. URL: https://doi.org/10.1137/S0097539795289859.
  6. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. URL: https://doi.org/10.1007/978-3-319-21275-3.
  7. Artur Czumaj, Magnús M Halldórsson, Andrzej Lingas, and Johan Nilsson. Approximation algorithms for optimization problems in graphs with superlogarithmic treewidth. Information processing letters, 94(2):49-53, 2005. Google Scholar
  8. Reinhard Diestel. Graph Theory, 4th Edition, volume 173 of Graduate texts in mathematics. Springer, 2012. Google Scholar
  9. Uriel Feige. Approximating maximum clique by removing subgraphs. SIAM Journal on Discrete Mathematics, 18(2):219-225, 2004. Google Scholar
  10. Uriel Feige, MohammadTaghi Hajiaghayi, and James R. Lee. Improved approximation algorithms for minimum weight vertex separators. SIAM J. Comput., 38(2):629-657, 2008. URL: https://doi.org/10.1137/05064299X.
  11. Magnús M. Halldórsson. Approximations of weighted independent set and hereditary subset problems. J. Graph Algorithms Appl., 4(1):1-16, 2000. URL: https://doi.org/10.7155/jgaa.00020.
  12. Magnús M. Halldórsson and Jaikumar Radhakrishnan. Improved approximations of independent sets in bounded-degree graphs via subgraph removal. Nord. J. Comput., 1(4):475-492, 1994. Google Scholar
  13. Eran Halperin. Improved approximation algorithms for the vertex cover problem in graphs and hypergraphs. In David B. Shmoys, editor, Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, January 9-11, 2000, San Francisco, CA, USA, pages 329-337. ACM/SIAM, 2000. URL: http://dl.acm.org/citation.cfm?id=338219.338269.
  14. Johan Hastad. Clique is hard to approximate within n/sup 1-/spl epsiv. In Proceedings of 37th Conference on Foundations of Computer Science, pages 627-636. IEEE, 1996. Google Scholar
  15. Subhash Khot and Ashok Kumar Ponnuswami. Better inapproximability results for maxclique, chromatic number and min-3lin-deletion. In Automata, Languages and Programming: 33rd International Colloquium, ICALP 2006, Venice, Italy, July 10-14, 2006, Proceedings, Part I 33, pages 226-237. Springer, 2006. Google Scholar
  16. Ton Kloks. Treewidth: computations and approximations. Springer, 1994. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact