Document Open Access Logo

ETH Tight Algorithms for Geometric Intersection Graphs: Now in Polynomial Space

Authors Fedor V. Fomin, Petr A. Golovach, Tanmay Inamdar, Saket Saurabh

PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2021.21.pdf
  • Filesize: 0.82 MB
  • 16 pages

Document Identifiers

Author Details

Fedor V. Fomin
  • University of Bergen, Norway
Petr A. Golovach
  • University of Bergen, Norway
Tanmay Inamdar
  • University of Bergen, Norway
Saket Saurabh
  • The Institute of Mathematical Sciences, HBNI, Chennai, India
  • University of Bergen, Norway

Funding

The research leading to these results has received funding from the Research Council of Norway via the project "`MULTIVAL" (grant no. 263317) and the European Research Council (ERC) via grant LOPPRE, reference 819416.

Cite As Get BibTex

Fedor V. Fomin, Petr A. Golovach, Tanmay Inamdar, and Saket Saurabh. ETH Tight Algorithms for Geometric Intersection Graphs: Now in Polynomial Space. In 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 213, pp. 21:1-21:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.FSTTCS.2021.21

Abstract

De Berg et al. in [SICOMP 2020] gave an algorithmic framework for subexponential algorithms on geometric graphs with tight (up to ETH) running times. This framework is based on dynamic programming on graphs of weighted treewidth resulting in algorithms that use super-polynomial space. We introduce the notion of weighted treedepth and use it to refine the framework of de Berg et al. for obtaining polynomial space (with tight running times) on geometric graphs. As a result, we prove that for any fixed dimension d ≥ 2 on intersection graphs of similarly-sized fat objects many well-known graph problems including Independent Set, r-Dominating Set for constant r, Cycle Cover, Hamiltonian Cycle, Hamiltonian Path, Steiner Tree, Connected Vertex Cover, Feedback Vertex Set, and (Connected) Odd Cycle Transversal are solvable in time 2^𝒪(n^{1-1/d}) and within polynomial space.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph algorithms
  • Theory of computation → Parameterized complexity and exact algorithms
Keywords
  • Subexponential Algorithms
  • Geometric Intersection Graphs
  • Treedepth
  • Treewidth

Metrics

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

Related Versions

References

  1. Steven Chaplick, Fedor V. Fomin, Petr A. Golovach, Dusan Knop, and Peter Zeman. Kernelization of graph hamiltonicity: Proper h-graphs. In Algorithms and Data Structures - 16th International Symposium, WADS 2019, Proceedings, volume 11646 of Lecture Notes in Computer Science, pages 296-310. Springer, 2019. URL: https://doi.org/10.1007/978-3-030-24766-9_22.
  2. Marek Cygan, Fedor V Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. Parameterized algorithms, volume 5. Springer, 2015. Google Scholar
  3. Marek Cygan, Jesper Nederlof, Marcin Pilipczuk, Michal Pilipczuk, Joham MM van Rooij, and Jakub Onufry Wojtaszczyk. Solving connectivity problems parameterized by treewidth in single exponential time. In 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, pages 150-159. IEEE, 2011. Google Scholar
  4. Mark de Berg, Hans L. Bodlaender, Sándor Kisfaludi-Bak, Dániel Marx, and Tom C. van der Zanden. A framework for exponential-time-hypothesis-tight algorithms and lower bounds in geometric intersection graphs. SIAM J. Comput., 49(6):1291-1331, 2020. URL: https://doi.org/10.1137/20M1320870.
  5. Mark de Berg, Sándor Kisfaludi-Bak, Morteza Monemizadeh, and Leonidas Theocharous. Clique-based separators for geometric intersection graphs. CoRR, abs/2109.09874, 2021. URL: http://arxiv.org/abs/2109.09874.
  6. 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. Journal of the ACM, 52(6):866-893, 2005. Google Scholar
  7. Reinhard Diestel. Graph Theory, 4th Edition, volume 173 of Graduate texts in mathematics. Springer, 2012. Google Scholar
  8. Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, and Meirav Zehavi. Finding, hitting and packing cycles in subexponential time on unit disk graphs. Discret. Comput. Geom., 62(4):879-911, 2019. URL: https://doi.org/10.1007/s00454-018-00054-x.
  9. Martin Fürer and Huiwen Yu. Space saving by dynamic algebraization based on tree-depth. Theory Comput. Syst., 61(2):283-304, 2017. URL: https://doi.org/10.1007/s00224-017-9751-3.
  10. Falko Hegerfeld and Stefan Kratsch. Solving connectivity problems parameterized by treedepth in single-exponential time and polynomial space. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS), volume 154 of LIPIcs, pages 29:1-29:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.STACS.2020.29.
  11. Hiro Ito and Masakazu Kadoshita. Tractability and intractability of problems on unit disk graphs parameterized by domain area. In Proceedings of the 9th International Symposium on Operations Research and Its Applications (ISORA), volume 2010. Citeseer, 2010. Google Scholar
  12. Sándor Kisfaludi-Bak. Hyperbolic intersection graphs and (quasi)-polynomial time. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1621-1638. SIAM, 2020. Google Scholar
  13. Donald Ervin Knuth. The art of computer programming: Generating all combinations and partitions. Addison-Wesley, 2005. Google Scholar
  14. Ketan Mulmuley, Umesh V Vazirani, and Vijay V Vazirani. Matching is as easy as matrix inversion. In Proceedings of the nineteenth annual ACM symposium on Theory of computing, pages 345-354, 1987. Google Scholar
  15. Jesper Nederlof, Michal Pilipczuk, Céline M. F. Swennenhuis, and Karol Wegrzycki. Hamiltonian cycle parameterized by treedepth in single exponential time and polynomial space. In 46th International Workshop on Graph-Theoretic Concepts in Computer Science (WG), volume 12301 of Lecture Notes in Computer Science, pages 27-39. Springer, 2020. URL: https://doi.org/10.1007/978-3-030-60440-0_3.
  16. Jesper Nederlof, Michal Pilipczuk, Céline M. F. Swennenhuis, and Karol Wegrzycki. Isolation schemes for problems on decomposable graphs. CoRR, abs/2105.01465, 2021. URL: http://arxiv.org/abs/2105.01465.
  17. 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.
  18. Bruce A Reed. Algorithmic aspects of tree width. In Recent advances in algorithms and combinatorics, pages 85-107. Springer, 2003. 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