Document Open Access Logo

Decomposition of Map Graphs with Applications

Authors Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Meirav Zehavi

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2019.60.pdf
  • Filesize: 0.62 MB
  • 15 pages

Document Identifiers

Author Details

Fedor V. Fomin
  • University of Bergen, Norway
Daniel Lokshtanov
  • University of California, Santa Barbara, USA
Fahad Panolan
  • University of Bergen, Norway
Saket Saurabh
  • The Institute of Mathematical Sciences, HBNI, Chennai, India
Meirav Zehavi
  • Ben-Gurion University of the Negev, Beer-Sheva, Israel

Acknowledgements

This work is supported by the European Research Council (ERC) via grant LOPPRE, reference 819416, the Norwegian Research Council via project MULTIVAL, and Israel Science Foundation individual research grant no. 1176/18.

Cite AsGet BibTex

Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, and Meirav Zehavi. Decomposition of Map Graphs with Applications. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 60:1-60:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ICALP.2019.60

Abstract

Bidimensionality is the most common technique to design subexponential-time parameterized algorithms on special classes of graphs, particularly planar graphs. The core engine behind it is a combinatorial lemma of Robertson, Seymour and Thomas that states that every planar graph either has a sqrt{k} x sqrt{k}-grid as a minor, or its treewidth is O(sqrt{k}). However, bidimensionality theory cannot be extended directly to several well-known classes of geometric graphs like unit disk or map graphs. This is mainly due to the presence of large cliques in these classes of graphs. Nevertheless, a relaxation of this lemma has been proven useful for unit disk graphs. Inspired by this, we prove a new decomposition lemma for map graphs, the intersection graphs of finitely many simply-connected and interior-disjoint regions of the Euclidean plane. Informally, our lemma states the following. For any map graph G, there exists a collection (U_1,...,U_t) of cliques of G with the following property: G either contains a sqrt{k} x sqrt{k}-grid as a minor, or it admits a tree decomposition where every bag is the union of O(sqrt{k}) cliques in the above collection. The new lemma appears to be a handy tool in the design of subexponential parameterized algorithms on map graphs. We demonstrate its usability by designing algorithms on map graphs with running time 2^{O({sqrt{k}log{k}})} * n^{O(1)} for Connected Planar F-Deletion (that encompasses problems such as Feedback Vertex Set and Vertex Cover). Obtaining subexponential algorithms for Longest Cycle/Path and Cycle Packing is more challenging. We have to construct tree decompositions with more powerful properties and to prove sublinear bounds on the number of ways an optimum solution could "cross" bags in these decompositions. For Longest Cycle/Path, these are the first subexponential-time parameterized algorithm on map graphs. For Feedback Vertex Set and Cycle Packing, we improve upon known 2^{O({k^{0.75}log{k}})} * n^{O(1)}-time algorithms on map graphs.

Subject Classification

ACM Subject Classification
  • Theory of computation → Parameterized complexity and exact algorithms
  • Theory of computation → Computational geometry
Keywords
  • Longest Cycle
  • Cycle Packing
  • Feedback Vertex Set
  • Map Graphs
  • FPT

Metrics

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

Related Versions

References

  1. J. Alber, H. L. Bodlaender, H. Fernau, T. Kloks, and R. Niedermeier. Fixed parameter algorithms for dominating set and related problems on planar graphs. Algorithmica, 33(4):461-493, 2002. Google Scholar
  2. Jochen Alber, Henning Fernau, and Rolf Niedermeier. Parameterized complexity: exponential speed-up for planar graph problems. J. Algorithms, 52(1):26-56, 2004. Google Scholar
  3. Noga Alon, Raphael Yuster, and Uri Zwick. Color-coding. J. Assoc. Comput. Mach., 42(4):844-856, 1995. Google Scholar
  4. Brenda S. Baker. Approximation algorithms for NP-complete problems on planar graphs. J. Assoc. Comput. Mach., 41(1):153-180, 1994. Google Scholar
  5. Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto. Narrow sieves for parameterized paths and packings. J. Comput. Syst. Sci., 87:119-139, 2017. URL: http://dx.doi.org/10.1016/j.jcss.2017.03.003.
  6. Zhi-Zhong Chen. Approximation algorithms for independent sets in map graphs. Journal of Algorithms, 41:20-40, 2001. Google Scholar
  7. Zhi-Zhong Chen, Enory Grigni, and Christos H. Papadimitriou. Planar map graphs. In Proceedings of the 30th Annual ACM Symposium on the Theory of Computing (STOC '98), pages 514-523. ACM, 1998. Google Scholar
  8. Zhi-Zhong Chen, Enory Grigni, and Christos H. Papadimitriou. Map graphs. J. Assoc. Comput. Mach., 49(2):127-138, 2002. Google Scholar
  9. Zhi-Zhong Chen, Michelangelo Grigni, and Christos H. Papadimitriou. Recognizing Hole-Free 4-Map Graphs in Cubic Time. Algorithmica, 45(2):227-262, 2006. URL: http://dx.doi.org/10.1007/s00453-005-1184-8.
  10. Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. Google Scholar
  11. Marek Cygan, Jesper Nederlof, Marcin Pilipczuk, Michal Pilipczuk, Johan M. M. van Rooij, and Jakub Onufry Wojtaszczyk. Solving connectivity problems parameterized by treewidth in single exponential time. In Proceedings of the 52nd Annual Symposium on Foundations of Computer Science (FOCS), pages 150-159. IEEE, 2011. Google Scholar
  12. Erik D. Demaine, Fedor V. Fomin, Mohammadtaghi Hajiaghayi, and Dimitrios M. Thilikos. Fixed-parameter algorithms for (k,r)-center in planar graphs and map graphs. ACM Trans. Algorithms, 1(1):33-47, 2005. URL: http://dx.doi.org/10.1145/1077464.1077468.
  13. Erik D. Demaine, Fedor V. Fomin, Mohammadtaghi Hajiaghayi, and Dimitrios M. Thilikos. Subexponential Parameterized Algorithms on Graphs of Bounded Genus and H-minor-free Graphs. J. ACM, 52(6):866-893, 2005. Google Scholar
  14. Erik D. Demaine and MohammadTaghi Hajiaghayi. Bidimensionality: new connections between FPT algorithms and PTASs. In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2005), pages 590-601, New York, 2005. ACM-SIAM. Google Scholar
  15. Erik D. Demaine and MohammadTaghi Hajiaghayi. The Bidimensionality Theory and Its Algorithmic Applications. Comput. J., 51(3):292-302, 2008. URL: http://dx.doi.org/10.1093/comjnl/bxm033.
  16. Reinhard Diestel. Graph Theory, 4th Edition, volume 173 of Graduate texts in mathematics. Springer, 2012. Google Scholar
  17. Frederic Dorn, Eelko Penninkx, Hans L. Bodlaender, and Fedor V. Fomin. Efficient Exact Algorithms on Planar Graphs: Exploiting Sphere Cut Decompositions. Algorithmica, 58(3):790-810, 2010. URL: http://dx.doi.org/10.1007/s00453-009-9296-1.
  18. Fedor V. Fomin, Daniel Lokshtanov, Neeldhara Misra, and Saket Saurabh. Planar F-Deletion: Approximation, Kernelization and Optimal FPT Algorithms. In Proceedings of the 53rd Annual Symposium on Foundations of Computer Science (FOCS), pages 470-479. IEEE, 2012. Google Scholar
  19. Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, and Saket Saurabh. Efficient Computation of Representative Families with Applications in Parameterized and Exact Algorithms. J. ACM, 63(4):29, 2016. URL: http://dx.doi.org/10.1145/2886094.
  20. Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, and Meirav Zehavi. Finding, Hitting and Packing Cycles in Subexponential Time on Unit Disk Graphs. Discrete & Computational Geometry, January 2019. URL: http://dx.doi.org/10.1007/s00454-018-00054-x.
  21. Fedor V. Fomin, Daniel Lokshtanov, and Saket Saurabh. Bidimensionality and geometric graphs. In Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1563-1575. SIAM, 2012. Google Scholar
  22. Fedor V. Fomin, Daniel Lokshtanov, and Saket Saurabh. Excluded grid minors and efficient polynomial-time approximation schemes. J. ACM, 65(2):Art. 10, 44, 2018. URL: http://dx.doi.org/10.1145/3154833.
  23. Qian-Ping Gu and Hisao Tamaki. Improved Bounds on the Planar Branchwidth with Respect to the Largest Grid Minor Size. Algorithmica, 64(3):416-453, November 2012. URL: http://dx.doi.org/10.1007/s00453-012-9627-5.
  24. Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity. Journal of Computer and System Sciences, 63(4):512-530, 2001. Google Scholar
  25. Ioannis Koutis. Faster Algebraic Algorithms for Path and Packing Problems. In Proceedings of the 35th International Colloquium on Automata, Languages and Programming (ICALP 2008), volume 5125 of Lecture Notes in Computer Science, pages 575-586, 2008. Google Scholar
  26. Ioannis Koutis and Ryan Williams. Algebraic fingerprints for faster algorithms. Commun. ACM, 59(1):98-105, 2016. URL: http://dx.doi.org/10.1145/2742544.
  27. Dániel Marx. The Square Root Phenomenon in Planar Graphs. In Proceedings of the 40th International Colloquium on Automata, Languages, and Programming (ICALP), volume 7966 of Lecture Notes in Computer Science, page 28. Springer, 2013. Google Scholar
  28. N. Robertson, P. Seymour, and R. Thomas. Quickly Excluding a Planar Graph. Journal of Combinatorial Theory, Series B, 62(2):323-348, 1994. URL: http://dx.doi.org/10.1006/jctb.1994.1073.
  29. Mikkel Thorup. Map Graphs In Polynomial Time. In Proceedings of the 39th Annual Symposium on Foundations of Computer Science (FOCS 1998), pages 396-405. IEEE Computer Society, 1998. Google Scholar
  30. Ryan Williams. Finding Paths of Length k in O^*(2^k) Time. Inf. Process. Lett., 109(6):315-318, 2009. 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 Imprint Privacy Contact