Document Open Access Logo

Approximation Metatheorems for Classes with Bounded Expansion

Author Zdeněk Dvořák

PDF
Thumbnail PDF

File

LIPIcs.SWAT.2022.22.pdf
  • Filesize: 0.75 MB
  • 17 pages

Document Identifiers

Author Details

Zdeněk Dvořák
  • Computer Science Institute, Charles University, Prague, Czech Republic

Funding

Supported by the ERC-CZ project LL2005 (Algorithms and complexity within and beyond bounded expansion) of the Ministry of Education of Czech Republic.

Cite As Get BibTex

Zdeněk Dvořák. Approximation Metatheorems for Classes with Bounded Expansion. In 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 227, pp. 22:1-22:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.SWAT.2022.22

Abstract

We give a number of approximation metatheorems for monotone maximization problems expressible in the first-order logic, in substantially more general settings than previously known. We obtain  
- a constant-factor approximation algorithm in any class of graphs with bounded expansion, 
- a QPTAS in any class with strongly sublinear separators, and 
- a PTAS in any fractionally treewidth-fragile class (which includes all common classes with strongly sublinear separators).
Moreover, our tools also give an exact subexponential-time algorithm in any class with strongly sublinear separators.

Subject Classification

ACM Subject Classification
  • Theory of computation → Approximation algorithms analysis
Keywords
  • bounded expansion
  • approximation
  • meta-algorithms

Metrics

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

Related Versions

References

  1. Saeed Akhoondian Amiri, Patrice Ossona de Mendez, Roman Rabinovich, and Sebastian Siebertz. Distributed domination on graph classes of bounded expansion. In Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures, SPAA '18, pages 143-151, New York, NY, USA, 2018. Association for Computing Machinery. Google Scholar
  2. Noga Alon, Paul Seymour, and Robin Thomas. A separator theorem for graphs with an excluded minor and its applications. In Proceedings of the twenty-second annual ACM symposium on Theory of computing, pages 293-299. ACM, 1990. Google Scholar
  3. B.S. Baker. Approximation algorithms for NP-complete problems on planar graphs. Journal of the ACM (JACM), 41(1):153-180, 1994. Google Scholar
  4. Piotr Berman and Marek Karpinski. On some tighter inapproximability results. In International Colloquium on Automata, Languages, and Programming, pages 200-209. Springer, 1999. Google Scholar
  5. Hans L Bodlaender. A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM Journal on computing, 25(6):1305-1317, 1996. Google Scholar
  6. Timothy M Chan, Elyot Grant, Jochen Könemann, and Malcolm Sharpe. Weighted capacitated, priority, and geometric set cover via improved quasi-uniform sampling. In Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete Algorithms, pages 1576-1585. SIAM, 2012. Google Scholar
  7. Bruno Courcelle. The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. Information and computation, 85(1):12-75, 1990. Google Scholar
  8. Anuj Dawar, Martin Grohe, Stephan Kreutzer, and Nicole Schweikardt. Approximation schemes for first-order definable optimisation problems. In 21st Annual IEEE Symposium on Logic in Computer Science (LICS'06), pages 411-420. IEEE, 2006. Google Scholar
  9. Erik D. Demaine and MohammadTaghi Hajiaghayi. Bidimensionality: new connections between FPT algorithms and PTASs. In Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, pages 590-601. Society for Industrial and Applied Mathematics, 2005. Google Scholar
  10. Matt DeVos, Guoli Ding, Bogdan Oporowski, Daniel Sanders, Bruce Reed, Paul Seymour, and Dirk Vertigan. Excluding any graph as a minor allows a low tree-width 2-coloring. J. Comb. Theory, Ser. B, 91:25-41, 2004. Google Scholar
  11. Pøal G. Drange, Markus Dregi, Fedor V. Fomin, Stephan Kreutzer, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Felix Reidl, Fernando Sánchez Villaamil, Saket Saurabh, Sebastian Siebertz, and Somnath Sikdar. Kernelization and Sparseness: the Case of Dominating Set. In 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016), volume 47 of Leibniz International Proceedings in Informatics (LIPIcs), pages 31:1-31:14, Dagstuhl, Germany, 2016. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. Google Scholar
  12. Z. Dvořák. Constant-factor approximation of domination number in sparse graphs. European Journal of Combinatorics, 34:833-840, 2013. Google Scholar
  13. Z. Dvořák. Sublinear separators, fragility and subexponential expansion. European Journal of Combinatorics, 52:103-119, 2016. Google Scholar
  14. Z. Dvořák. On classes of graphs with strongly sublinear separators. European Journal of Combinatorics, 71:1-11, 2018. Google Scholar
  15. Z. Dvořák. On distance r-dominating and 2r-independent sets in sparse graphs. J. Graph Theory, 91(2):162-173, 2019. Google Scholar
  16. Z. Dvořák. Baker game and polynomial-time approximation schemes. In Proceedings of the Thirty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '20, pages 2227-2240. Society for Industrial and Applied Mathematics, 2020. Google Scholar
  17. Z. Dvořák, Daniel Král', and Robin Thomas. Testing first-order properties for subclasses of sparse graphs. Journal of the ACM (JACM), 60(5):36, 2013. Google Scholar
  18. Z. Dvořák and Sergey Norin. Strongly sublinear separators and polynomial expansion. SIAM Journal on Discrete Mathematics, 30:1095-1101, 2016. Google Scholar
  19. Zdeněk Dvořák. Thin graph classes and polynomial-time approximation schemes. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'18), pages 1685-1701. ACM, 2018. Google Scholar
  20. Zdeněk Dvořák and Abhiruk Lahiri. Approximation schemes for bounded distance problems on fractionally treewidth-fragile graphs. arXiv, 2105.01780, 2021. URL: http://arxiv.org/abs/2105.01780.
  21. Carl Einarson and Felix Reidl. A General Kernelization Technique for Domination and Independence Problems in Sparse Classes. In 15th International Symposium on Parameterized and Exact Computation (IPEC 2020), volume 180 of Leibniz International Proceedings in Informatics (LIPIcs), pages 11:1-11:15, Dagstuhl, Germany, 2020. Schloss Dagstuhl-Leibniz-Zentrum für Informatik. Google Scholar
  22. Thomas Erlebach, Klaus Jansen, and Eike Seidel. Polynomial-time approximation schemes for geometric intersection graphs. SIAM Journal on Computing, 34:1302-1323, 2005. Google Scholar
  23. Uriel Feige, MohammadTaghi Hajiaghayi, and James R Lee. Improved approximation algorithms for minimum weight vertex separators. SIAM Journal on Computing, 38(2):629-657, 2008. Google Scholar
  24. Jakub Gajarský, Stephan Kreutzer, Jaroslav Nešetřil, Patrice Ossona De Mendez, Michał Pilipczuk, Sebastian Siebertz, and Szymon Toruńczyk. First-order interpretations of bounded expansion classes. ACM Transactions on Computational Logic (TOCL), 21(4):1-41, 2020. Google Scholar
  25. Martin Grohe and Stephan Kreutzer. Methods for algorithmic meta theorems. Model Theoretic Methods in Finite Combinatorics, 558:181-206, 2011. Google Scholar
  26. Martin Grohe, Stephan Kreutzer, and Sebastian Siebertz. Deciding first-order properties of nowhere dense graphs. In Proceedings of the 46th Annual ACM Symposium on Theory of Computing, pages 89-98. ACM, 2014. Google Scholar
  27. Sariel Har-Peled and Kent Quanrud. Approximation algorithms for polynomial-expansion and low-density graphs. In Algorithms-ESA 2015, pages 717-728. Springer, 2015. Google Scholar
  28. Stephan Kreutzer, Roman Rabinovich, and Sebastian Siebertz. Polynomial kernels and wideness properties of nowhere dense graph classes. ACM Transactions on Algorithms (TALG), 15(2):24, 2018. Google Scholar
  29. R. Lipton and R. Tarjan. A separator theorem for planar graphs. SIAM Journal on Applied Mathematics, 36:177-189, 1979. Google Scholar
  30. R. Lipton and R. Tarjan. Applications of a planar separator theorem. SIAM Journal on Computing, 9:615-627, 1980. Google Scholar
  31. Gary L Miller, Shang-Hua Teng, William Thurston, and Stephen A Vavasis. Separators for sphere-packings and nearest neighbor graphs. Journal of the ACM (JACM), 44(1):1-29, 1997. Google Scholar
  32. J. Nešetřil and P. Ossona de Mendez. Grad and classes with bounded expansion I. Decompositions. European J. Combin., 29:760-776, 2008. Google Scholar
  33. J. Nešetřil and P. Ossona de Mendez. Grad and classes with bounded expansion II. Algorithmic aspects. European J. Combin., 29:777-791, 2008. Google Scholar
  34. J. Nešetřil and P. Ossona de Mendez. First order properties on nowhere dense structures. J. Symbolic Logic, 75:868-887, 2010. Google Scholar
  35. J. Nešetřil and P. Ossona de Mendez. Sparsity (Graphs, Structures, and Algorithms), volume 28 of Algorithms and Combinatorics. Springer, 2012. Google Scholar
  36. J. Nešetřil, P. Ossona de Mendez, and D. Wood. Characterisations and examples of graph classes with bounded expansion. Eur. J. Comb., 33:350-373, 2012. Google Scholar
  37. Michał Pilipczuk, Sebastian Siebertz, and Szymon Toruńczyk. Parameterized circuit complexity of model-checking on sparse structures. In Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science, pages 789-798, 2018. Google Scholar
  38. Felix Reidl, Fernando Sánchez Villaamil, and Konstantinos Stavropoulos. Characterising bounded expansion by neighbourhood complexity. European Journal of Combinatorics, 75:152-168, 2019. Google Scholar
  39. Szymon Toruńczyk. Aggregate queries on sparse databases. In Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, pages 427-443, 2020. Google Scholar
  40. David Zuckerman. Linear degree extractors and the inapproximability of Max Clique and Chromatic Number. Theory of Computing, 3:103-128, 2007. 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-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact