Document Open Access Logo

Space-Efficient Parameterized Algorithms on Graphs of Low Shrubdepth

Authors Benjamin Bergougnoux, Vera Chekan , Robert Ganian , Mamadou Moustapha Kanté , Matthias Mnich , Sang-il Oum , Michał Pilipczuk, Erik Jan van Leeuwen

PDF
Thumbnail PDF

File

LIPIcs.ESA.2023.18.pdf
  • Filesize: 1.77 MB
  • 18 pages

Document Identifiers

Author Details

Benjamin Bergougnoux
  • Institute of Informatics, University of Warsaw, Poland
Vera Chekan
  • Humboldt-Universität zu Berlin, Germany
Robert Ganian
  • Algorithms and Complexity Group, TU Wien, Austria
Mamadou Moustapha Kanté
  • Université Clermont Auvergne, Clermont Auvergne INP, LIMOS, CNRS, Clermont-Ferrand, France
Matthias Mnich
  • Hamburg University of Technology, Institute for Algorithms and Complexity, Germany
Sang-il Oum
  • Discrete Mathematics Group, Institute for Basic Science (IBS), Daejeon, Korea
  • Department of Mathematical Sciences, KAIST, Daejeon, Korea
Michał Pilipczuk
  • Institute of Informatics, University of Warsaw, Poland
Erik Jan van Leeuwen
  • Dept. Information and Computing Sciences, Utrecht University, The Netherlands

Funding

  • Chekan, Vera: Supported by the DFG Research Training Group 2434 "Facets of Complexity".
  • Ganian, Robert: Project No. Y1329 of the Austrian Science Fund (FWF), WWTF Project ICT22-029.
  • Kanté, Mamadou Moustapha: Supported by the French National Research Agency (ANR-18-CE40-0025-01 and ANR-20-CE48-0002).
  • Oum, Sang-il: Supported by the Institute for Basic Science (IBS-R029-C1).
  • Pilipczuk, Michał: This work is a part of project BOBR that has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No. 948057).

Acknowledgements

This work was initiated at the Graph Decompositions: Small Width, Big Challenges workshop held at the Lorentz Center in Leiden, The Netherlands, in 2022.

Cite As Get BibTex

Benjamin Bergougnoux, Vera Chekan, Robert Ganian, Mamadou Moustapha Kanté, Matthias Mnich, Sang-il Oum, Michał Pilipczuk, and Erik Jan van Leeuwen. Space-Efficient Parameterized Algorithms on Graphs of Low Shrubdepth. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 18:1-18:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.ESA.2023.18

Abstract

Dynamic programming on various graph decompositions is one of the most fundamental techniques used in parameterized complexity. Unfortunately, even if we consider concepts as simple as path or tree decompositions, such dynamic programming uses space that is exponential in the decomposition’s width, and there are good reasons to believe that this is necessary. However, it has been shown that in graphs of low treedepth it is possible to design algorithms which achieve polynomial space complexity without requiring worse time complexity than their counterparts working on tree decompositions of bounded width. Here, treedepth is a graph parameter that, intuitively speaking, takes into account both the depth and the width of a tree decomposition of the graph, rather than the width alone.
Motivated by the above, we consider graphs that admit clique expressions with bounded depth and label count, or equivalently, graphs of low shrubdepth. Here, shrubdepth is a bounded-depth analogue of cliquewidth, in the same way as treedepth is a bounded-depth analogue of treewidth. We show that also in this setting, bounding the depth of the decomposition is a deciding factor for improving the space complexity. More precisely, we prove that on n-vertex graphs equipped with a tree-model (a decomposition notion underlying shrubdepth) of depth d and using k labels,  
- Independent Set can be solved in time 2^𝒪(dk) ⋅ n^𝒪(1) using 𝒪(dk²log n) space; 
- Max Cut can be solved in time n^𝒪(dk) using 𝒪(dk log n) space; and 
- Dominating Set can be solved in time 2^𝒪(dk) ⋅ n^𝒪(1) using n^𝒪(1) space via a randomized algorithm.  We also establish a lower bound, conditional on a certain assumption about the complexity of Longest Common Subsequence, which shows that at least in the case of Independent Set the exponent of the parametric factor in the time complexity has to grow with d if one wishes to keep the space complexity polynomial.

Subject Classification

ACM Subject Classification
  • Theory of computation → Parameterized complexity and exact algorithms
Keywords
  • Parameterized complexity
  • shrubdepth
  • space complexity
  • algebraic methods

Metrics

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

Related Versions

References

  1. Amir Abboud, Arturs Backurs, and Virginia Vassilevska Williams. Tight hardness results for LCS and other sequence similarity measures. In Proc. FOCS 2015, pages 59-78, 2015. URL: https://doi.org/10.1109/FOCS.2015.14.
  2. Eric Allender, Shiteng Chen, Tiancheng Lou, Periklis A. Papakonstantinou, and Bangsheng Tang. Width-parametrized SAT: Time-space tradeoffs. Theory Comput., 10(12):297-339, 2014. URL: https://doi.org/10.4086/toc.2014.v010a012.
  3. Marina Barsky, Ulrike Stege, Alex Thomo, and Chris Upton. Shortest path approaches for the longest common subsequence of a set of strings. In Proc. BIBE 2007, pages 327-333, 2007. URL: https://doi.org/10.1109/BIBE.2007.4375584.
  4. Cristina Bazgan, Morgan Chopin, Marek Cygan, Michael R. Fellows, Fedor V. Fomin, and Erik Jan van Leeuwen. Parameterized complexity of firefighting. J. Comput. System Sci., 80(7):1285-1297, 2014. URL: https://doi.org/10.1016/j.jcss.2014.03.001.
  5. Benjamin Bergougnoux, Vera Chekan, Robert Ganian, Mamadou Moustapha Kanté, Matthias Mnich, Sang il Oum, Michał Pilipczuk, and Erik Jan van Leeuwen. Space-efficient parameterized algorithms on graphs of low shrubdepth. arXiv, 2023. URL: https://doi.org/10.48550/arXiv.2307.01285.
  6. Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto. Fourier meets Möbius: fast subset convolution. In Proc. STOC 2007, pages 67-74, 2007. Google Scholar
  7. Janka Chlebíková and Morgan Chopin. The firefighter problem: further steps in understanding its complexity. Theoret. Comput. Sci., 676:42-51, 2017. URL: https://doi.org/10.1016/j.tcs.2017.03.004.
  8. Bruno Courcelle, Johann A. Makowsky, and Udi Rotics. Linear time solvable optimization problems on graphs of bounded clique-width. Theory Comput. Syst., 33(2):125-150, 2000. URL: https://doi.org/10.1007/s002249910009.
  9. 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
  10. Matt DeVos, O-joung Kwon, and Sang-il Oum. Branch-depth: Generalizing tree-depth of graphs. European J. Combin., 90:Article 103186, 2020. Google Scholar
  11. Reinhard Diestel. Graph Theory, volume 173 of Graduate texts in mathematics. Springer, 4th edition, 2012. Google Scholar
  12. Rodney G. Downey and Michael R. Fellows. Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, 2013. URL: https://doi.org/10.1007/978-1-4471-5559-1.
  13. Jan Dreier. Lacon- and shrub-decompositions: A new characterization of first-order transductions of bounded expansion classes. In Proc. LICS 2021, pages 1-13, 2021. URL: https://doi.org/10.1109/LICS52264.2021.9470680.
  14. Jan Dreier, Jakub Gajarský, Sandra Kiefer, Michał Pilipczuk, and Szymon Toruńczyk. Treelike decompositions for transductions of sparse graphs. In Proc. LICS 2022, pages 31:1-31:14, 2022. URL: https://doi.org/10.1145/3531130.3533349.
  15. Michael Elberfeld, Christoph Stockhusen, and Till Tantau. On the space and circuit complexity of parameterized problems: Classes and completeness. Algorithmica, 71(3):661-701, 2015. URL: https://doi.org/10.1007/s00453-014-9944-y.
  16. Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, and Saket Saurabh. Intractability of clique-width parameterizations. SIAM J. Comput., 39(5):1941-1956, 2010. URL: https://doi.org/10.1137/080742270.
  17. Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, and Saket Saurabh. Almost optimal lower bounds for problems parameterized by clique-width. SIAM J. Comput., 43(5):1541-1563, 2014. URL: https://doi.org/10.1137/130910932.
  18. Fedor V. Fomin and Tuukka Korhonen. Fast FPT-approximation of branchwidth. In Proc. STOC 2022, pages 886-899, 2022. Google Scholar
  19. Martin Fürer. Multi-clique-width. In Proc. ITCS 2017, volume 67 of Leibniz Int. Proc. Inform., pages 14:1-14:13, 2017. URL: https://doi.org/10.4230/LIPIcs.ITCS.2017.14.
  20. 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.
  21. Jakub Gajarský and Stephan Kreutzer. Computing shrub-depth decompositions. In Proc. STACS 2020, volume 154 of Leibniz Int. Proc. Inform., pages 56:1-56:17, 2020. URL: https://doi.org/10.4230/LIPIcs.STACS.2020.56.
  22. 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 Trans. Comput. Log., 21(4):Art. 29, 41, 2020. URL: https://doi.org/10.1145/3382093.
  23. Robert Ganian, Petr Hliněný, Jaroslav Nešetřil, Jan Obdržálek, and Patrice Ossona de Mendez. Shrub-depth: Capturing height of dense graphs. Log. Methods Comput. Sci., 15(1):7:1-7:25, 2019. URL: https://doi.org/10.23638/LMCS-15(1:7)2019.
  24. Tatsuya Gima, Tesshu Hanaka, Masashi Kiyomi, Yasuaki Kobayashi, and Yota Otachi. Exploring the gap between treedepth and vertex cover through vertex integrity. Theoret. Comput. Sci., 918:60-76, 2022. URL: https://doi.org/10.1016/j.tcs.2022.03.021.
  25. Falko Hegerfeld and Stefan Kratsch. Solving connectivity problems parameterized by treedepth in single-exponential time and polynomial space. In Proc. STACS 2020, volume 154 of Leibniz Int. Proc. Inform., 2020. Google Scholar
  26. Falko Hegerfeld and Stefan Kratsch. Tight algorithms for connectivity problems parameterized by clique-width. arXiv, 2023. URL: https://doi.org/10.48550/ARXIV.2302.03627.
  27. Daniel M. Kane. Unary subset-sum is in logspace. arXiv, 2010. URL: https://arxiv.org/abs/1012.1336.
  28. Shaohua Li and Marcin Pilipczuk. Hardness of metric dimension in graphs of constant treewidth. Algorithmica, 84(11):3110-3155, 2022. URL: https://doi.org/10.1007/s00453-022-01005-y.
  29. Daniel Lokshtanov, Matthias Mnich, and Saket Saurabh. Planar k-path in subexponential time and polynomial space. In Proc. WG 2011, volume 6986 of Lecture Notes Comput. Sci., pages 262-270, 2011. URL: https://doi.org/10.1007/978-3-642-25870-1_24.
  30. Ketan Mulmuley, Umesh V. Vazirani, and Vijay V. Vazirani. Matching is as easy as matrix inversion. Combinatorica, 7(1):105-113, 1987. URL: https://doi.org/10.1007/BF02579206.
  31. Wojciech Nadara, Michał Pilipczuk, and Marcin Smulewicz. Computing treedepth in polynomial space and linear FPT time. In Proc. ESA 2022, volume 244 of Leibniz Int. Proc. Inform., pages 79:1-79:14, 2022. URL: https://doi.org/10.4230/lipics.esa.2022.79.
  32. Jesper Nederlof, Michał Pilipczuk, Céline M. F. Swennenhuis, and Karol Węgrzycki. Hamiltonian cycle parameterized by treedepth in single exponential time and polynomial space. In Proc. WG 2020, volume 12301 of Lecture Notes Comput. Sci., pages 27-39, 2020. URL: https://doi.org/10.1007/978-3-030-60440-0_3.
  33. Pierre Ohlmann, Michał Pilipczuk, Wojciech Przybyszewski, and Szymon Toruńczyk. Canonical decompositions in monadically stable and bounded shrubdepth graph classes. arXiv, 2023. URL: https://doi.org/10.48550/arXiv.2303.01473.
  34. Patrice Ossona de Mendez, Michał Pilipczuk, and Sebastian Siebertz. Transducing paths in graph classes with unbounded shrubdepth. European J. Combin., page 103660, 2022. URL: https://doi.org/10.1016/j.ejc.2022.103660.
  35. Michał Pilipczuk and Marcin Wrochna. On space efficiency of algorithms working on structural decompositions of graphs. ACM Trans. Comput. Theory, 9(4):18:1-18:36, 2018. URL: https://doi.org/10.1145/3154856.
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