Document Open Access Logo

Approximation Schemes for Bounded Distance Problems on Fractionally Treewidth-Fragile Graphs

Authors Zdeněk Dvořák , Abhiruk Lahiri

PDF
Thumbnail PDF

File

LIPIcs.ESA.2021.40.pdf
  • Filesize: 0.64 MB
  • 10 pages

Document Identifiers

Author Details

Zdeněk Dvořák
  • Charles University, Prague, Czech Republic
Abhiruk Lahiri
  • Ariel University, Israel

Funding

  • Dvořák, Zdeněk: Supported by the ERC-CZ project LL2005 (Algorithms and complexity within and beyond bounded expansion) of the Ministry of Education of Czech Republic.
  • Lahiri, Abhiruk: Supported by ISF grant 822/18 and Ariel University Post-doctoral fellowship.

Acknowledgements

The second author wish to thank the Caesarea Rothschild Institute and the Department of Computer Science, University of Haifa, for providing its facilities for his research activities.

Cite AsGet BibTex

Zdeněk Dvořák and Abhiruk Lahiri. Approximation Schemes for Bounded Distance Problems on Fractionally Treewidth-Fragile Graphs. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 40:1-40:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.ESA.2021.40

Abstract

We give polynomial-time approximation schemes for monotone maximization problems expressible in terms of distances (up to a fixed upper bound) and efficiently solvable on graphs of bounded treewidth. These schemes apply in all fractionally treewidth-fragile graph classes, a property which is true for many natural graph classes with sublinear separators. We also provide quasipolynomial-time approximation schemes for these problems in all classes with sublinear separators.

Subject Classification

ACM Subject Classification
  • Theory of computation → Approximation algorithms analysis
Keywords
  • approximation
  • sublinear separators

Metrics

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

Related Versions

References

  1. Vladimir E. Alekseev, Vadim V. Lozin, Dmitriy S. Malyshev, and Martin Milanic. The maximum independent set problem in planar graphs. In Mathematical Foundations of Computer Science 2008, 33rd International Symposium, MFCS 2008, Torun, Poland, August 25-29, 2008, Proceedings, volume 5162 of Lecture Notes in Computer Science, pages 96-107. Springer, 2008. URL: https://doi.org/10.1007/978-3-540-85238-4_7.
  2. Noga Alon, Paul D. Seymour, and Robin Thomas. A separator theorem for graphs with an excluded minor and its applications. In Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, May 13-17, 1990, Baltimore, Maryland, USA, pages 293-299. ACM, 1990. URL: https://doi.org/10.1145/100216.100254.
  3. Brenda S. Baker. Approximation algorithms for np-complete problems on planar graphs. J. ACM, 41(1):153-180, 1994. URL: https://doi.org/10.1145/174644.174650.
  4. Piotr Berman and Marek Karpinski. On some tighter inapproximability results (extended abstract). In Automata, Languages and Programming, 26th International Colloquium, ICALP'99, Prague, Czech Republic, July 11-15, 1999, Proceedings, volume 1644 of Lecture Notes in Computer Science, pages 200-209. Springer, 1999. URL: https://doi.org/10.1007/3-540-48523-6_17.
  5. Bruno Courcelle. The monadic second-order logic of graphs. i. recognizable sets of finite graphs. Inf. Comput., 85(1):12-75, 1990. URL: https://doi.org/10.1016/0890-5401(90)90043-H.
  6. Anuj Dawar, Martin Grohe, Stephan Kreutzer, and Nicole Schweikardt. Approximation schemes for first-order definable optimisation problems. In 21th IEEE Symposium on Logic in Computer Science (LICS 2006), 12-15 August 2006, Seattle, WA, USA, Proceedings, pages 411-420. IEEE Computer Society, 2006. URL: https://doi.org/10.1109/LICS.2006.13.
  7. Erik D. Demaine and Mohammad Taghi Hajiaghayi. Bidimensionality: new connections between FPT algorithms and ptass. In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2005, Vancouver, British Columbia, Canada, January 23-25, 2005, pages 590-601. SIAM, 2005. URL: http://dl.acm.org/citation.cfm?id=1070432.1070514.
  8. Matt DeVos, Guoli Ding, Bogdan Oporowski, Daniel P. Sanders, Bruce A. Reed, Paul D. Seymour, and Dirk Vertigan. Excluding any graph as a minor allows a low tree-width 2-coloring. J. Comb. Theory, Ser. B, 91(1):25-41, 2004. URL: https://doi.org/10.1016/j.jctb.2003.09.001.
  9. Zdenek Dvorák. Sublinear separators, fragility and subexponential expansion. Eur. J. Comb., 52:103-119, 2016. URL: https://doi.org/10.1016/j.ejc.2015.09.001.
  10. Zdenek Dvorák. On classes of graphs with strongly sublinear separators. Eur. J. Comb., 71:1-11, 2018. URL: https://doi.org/10.1016/j.ejc.2018.02.032.
  11. Zdenek Dvorák. Thin graph classes and polynomial-time approximation schemes. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 1685-1701. SIAM, 2018. URL: https://doi.org/10.1137/1.9781611975031.110.
  12. Zdenek Dvorák. Baker game and polynomial-time approximation schemes. In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, pages 2227-2240. SIAM, 2020. URL: https://doi.org/10.1137/1.9781611975994.137.
  13. Zdenek Dvorák. Approximation metatheorem for fractionally treewidth-fragile graphs. CoRR, abs/2103.08698, 2021. URL: http://arxiv.org/abs/2103.08698.
  14. Zdenek Dvorák and Sergey Norin. Strongly sublinear separators and polynomial expansion. SIAM J. Discret. Math., 30(2):1095-1101, 2016. URL: https://doi.org/10.1137/15M1017569.
  15. Thomas Erlebach, Klaus Jansen, and Eike Seidel. Polynomial-time approximation schemes for geometric intersection graphs. SIAM J. Comput., 34(6):1302-1323, 2005. URL: https://doi.org/10.1137/S0097539702402676.
  16. Sariel Har-Peled and Kent Quanrud. Approximation algorithms for polynomial-expansion and low-density graphs. SIAM J. Comput., 46(6):1712-1744, 2017. URL: https://doi.org/10.1137/16M1079336.
  17. Lukasz Kowalik and Maciej Kurowski. Oracles for bounded-length shortest paths in planar graphs. ACM Trans. Algorithms, 2(3):335-363, 2006. URL: https://doi.org/10.1145/1159892.1159895.
  18. Robert Krauthgamer and James R. Lee. The intrinsic dimensionality of graphs. Comb., 27(5):551-585, 2007. URL: https://doi.org/10.1007/s00493-007-2183-y.
  19. Richard J. Lipton and Robert Endre Tarjan. A separator theorem for planar graphs. SIAM J. Appl. Math., 36(2):177-189, 1979. URL: https://doi.org/10.1137/0136016.
  20. Richard J. Lipton and Robert Endre Tarjan. Applications of a planar separator theorem. SIAM J. Comput., 9(3):615-627, 1980. URL: https://doi.org/10.1137/0209046.
  21. Gary L. Miller, Shang-Hua Teng, William P. Thurston, and Stephen A. Vavasis. Separators for sphere-packings and nearest neighbor graphs. J. ACM, 44(1):1-29, 1997. URL: https://doi.org/10.1145/256292.256294.
  22. Jaroslav Nesetril and Patrice Ossona de Mendez. Grad and classes with bounded expansion II. algorithmic aspects. Eur. J. Comb., 29(3):777-791, 2008. URL: https://doi.org/10.1016/j.ejc.2006.07.014.
  23. Jaroslav Nesetril and Patrice Ossona de Mendez. Sparsity - Graphs, Structures, and Algorithms, volume 28 of Algorithms and combinatorics. Springer, 2012. URL: https://doi.org/10.1007/978-3-642-27875-4.
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 Imprint Privacy Contact