Document Open Access Logo

Sublinear-Space Lexicographic Depth-First Search for Bounded Treewidth Graphs and Planar Graphs

Authors Taisuke Izumi, Yota Otachi

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2020.67.pdf
  • Filesize: 0.71 MB
  • 17 pages

Document Identifiers

Author Details

Taisuke Izumi
  • Nagoya Institute of Technology, Japan
Yota Otachi
  • Nagoya University, Japan

Funding

  • Izumi, Taisuke: JSPS KAKENHI Grant Number 19K11824
  • Otachi, Yota: JSPS KAKENHI Grant Numbers JP18H04091, JP18K11168, JP18K11169

Cite As Get BibTex

Taisuke Izumi and Yota Otachi. Sublinear-Space Lexicographic Depth-First Search for Bounded Treewidth Graphs and Planar Graphs. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 67:1-67:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.ICALP.2020.67

Abstract

The lexicographic depth-first search (Lex-DFS) is one of the first basic graph problems studied in the context of space-efficient algorithms. It is shown independently by Asano et al. [ISAAC 2014] and Elmasry et al. [STACS 2015] that Lex-DFS admits polynomial-time algorithms that run with O(n)-bit working memory, where n is the number of vertices in the graph. Lex-DFS is known to be P-complete under logspace reduction, and giving or ruling out polynomial-time sublinear-space algorithms for Lex-DFS on general graphs is quite challenging. In this paper, we study Lex-DFS on graphs of bounded treewidth. We first show that given a tree decomposition of width O(n^(1-ε)) with ε > 0, Lex-DFS can be solved in sublinear space. We then complement this result by presenting a space-efficient algorithm that can compute, for w ≤ √n, a tree decomposition of width O(w √nlog n) or correctly decide that the graph has a treewidth more than w. This algorithm itself would be of independent interest as the first space-efficient algorithm for computing a tree decomposition of moderate (small but non-constant) width. By combining these results, we can show in particular that graphs of treewidth O(n^(1/2 - ε)) for some ε > 0 admits a polynomial-time sublinear-space algorithm for Lex-DFS. We can also show that planar graphs admit a polynomial-time algorithm with O(n^(1/2+ε))-bit working memory for Lex-DFS.

Subject Classification

ACM Subject Classification
  • Theory of computation → Problems, reductions and completeness
  • Theory of computation → Complexity classes
  • Theory of computation → Graph algorithms analysis
  • Mathematics of computing → Graph algorithms
Keywords
  • depth-first search
  • space complexity
  • treewidth

Metrics

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

References

  1. Eric Allender, David A. Mix Barrington, Tanmoy Chakraborty, Samir Datta, and Sambuddha Roy. Planar and grid graph reachability problems. Theory of Computing Systems., 45(4):675–723, 2009. Google Scholar
  2. Richard Anderson and Ernst W. Mayr. Parallelism and the maximal path problem. Information Processing Letters, 24(2):121-126, 1987. URL: https://doi.org/10.1016/0020-0190(87)90105-0.
  3. Tetsuo Asano, Taisuke Izumi, Masashi Kiyomi, Matsuo Konagaya, Hirotaka Ono, Yota Otachi, Pascal Schweitzer, Jun Tarui, and Ryuhei Uehara. Depth-first search using O(n) bits. In International Symposium on Algorithms and Computation (ISAAC), pages 553-564, 2014. Google Scholar
  4. Tetsuo Asano, David Kirkpatrick, Kotaro Nakagawa, and Osamu Watanabe. Õ(√n)-space and polynomial-time algorithm for planar directed graph reachability. In International Symposium on Mathematical Foundations of Computer Science (MFCS), pages 45-56, 2014. Google Scholar
  5. Ryo Ashida and Kotaro Nakagawa. Õ(n^1/3)-space algorithm for the grid graph reachability problem. In International Symposium on Computational Geometry (SoCG), pages 5:1-5:13, 2018. Google Scholar
  6. Niranka Banerjee, Sankardeep Chakraborty, and Venkatesh Raman. Improved space efficient algorithms for BFS, DFS and applications. In International Computing and Combinatorics Conference (COCOON), pages 119-130, 2016. Google Scholar
  7. Bahareh Banyassady, Matias Korman, Wolfgang Mulzer, André van Renssen, Marcel Roeloffzen, Paul Seiferth, and Yannik Stein. Improved Time-Space Trade-Offs for Computing Voronoi Diagrams. In International Symposium on Theoretical Aspects of Computer Science (STACS), pages 9:1-9:14, 2017. URL: https://doi.org/10.4230/LIPIcs.STACS.2017.9.
  8. Luis Barba, Matias Korman, Stefan Langerman, Kunihiko Sadakane, and Rodrigo I. Silveira. Space-time trade-offs for stack-based algorithms. Algorithmica, 72(4):1097-1129, 2015. URL: https://doi.org/10.1007/s00453-014-9893-5.
  9. Greg Barnes, Jonathan F. Buss, Walter L. Ruzzo, and Baruch Schieber. A sublinear space, polynomial time algorithm for directed s-t connectivity. SIAM Journal on Computing, 27(5):1273-1282, 1998. URL: https://doi.org/10.1137/S0097539793283151.
  10. Allan B. Borodin and Stephan Cook. A time-space tradeoff for sorting on a general sequential model of computation. SIAM Journal on Computing, 11(2):287-297, 1982. URL: https://doi.org/10.1137/0211022.
  11. Harry Buhrman, Richard Cleve, Michal Koucký, Bruno Loff, and Florian Speelman. Computing with a full memory: Catalytic space. In ACM Symposium on Theory of Computing (STOC), pages 857-866, 2014. URL: https://doi.org/10.1145/2591796.2591874.
  12. Diptarka Chakraborty, A. Pavan, Raghunath Tewari, N. Variyam Vinodchandran, and Lin Forrest Yang. New Time-Space Upperbounds for Directed Reachability in High-genus and H-minor-free Graphs. In International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS), pages 585-595, 2014. Google Scholar
  13. Diptarka Chakraborty and Raghunath Tewari. An O(n^ε) space and polynomial time algorithm for reachability in directed layered planar graphs. ACM Transactions on Computation Theory, 9(4), 2017. Google Scholar
  14. Sankardeep Chakraborty, Anish Mukherjee, Venkatesh Raman, and Srinivasa Rao Satti. A Framework for In-place Graph Algorithms. In European Symposium on Algorithms (ESA), volume 112, pages 13:1-13:16, 2018. URL: https://doi.org/10.4230/LIPIcs.ESA.2018.13.
  15. Sankardeep Chakraborty, Venkatesh Raman, and Srinivasa Rao Satti. Biconnectivity, Chain Decomposition and st-Numbering Using O(n) Bits. In International Symposium on Algorithms and Computation (ISAAC), volume 64, pages 22:1-22:13, 2016. URL: https://doi.org/10.4230/LIPIcs.ISAAC.2016.22.
  16. Sankardeep Chakraborty and Srinivasa Rao Satti. Space-efficient algorithms for maximum cardinality search, its applications, and variants of bfs. Jouanal of Combinatorial Optimization, 37(2):465-481, 2019. URL: https://doi.org/10.1007/s10878-018-0270-1.
  17. Timothy M. Chan. Comparison-based time-space lower bounds for selection. ACM Transactions on Algorithms, 6(2):26:1-26:16, 2010. URL: https://doi.org/10.1145/1721837.1721842.
  18. Timothy M. Chan, J. Ian Munro, and Venkatesh Raman. Faster, space-efficient selection algorithms in read-only memory for integers. In International Symposium on Algorithms and Computation (ISAAC), pages 405-412, 2013. URL: https://doi.org/10.1007/978-3-642-45030-3_38.
  19. Bruno Courcelle. The monadic second-order logic of graphs. i. recognizable sets of finite graphs. Information and Computation, 85(1):12-75, 1990. URL: https://doi.org/10.1016/0890-5401(90)90043-H.
  20. Omar Darwish and Amr Elmasry. Optimal time-space tradeoff for the 2D convex-hull problem. In European Symposium on Algorithms (ESA), pages 284-295, 2014. Google Scholar
  21. Jeff Edmonds, Chung Keung Poon, and Dimitris Achlioptas. Tight lower bounds for st-connectivity on the nnjag model. SIAM Journal on Computing, 28(6):2257-2284, 1999. URL: https://doi.org/10.1137/S0097539795295948.
  22. Michael Elberfeld, Andreas Jakoby, and Till Tantau. Logspace versions of the theorems of Bodlaender and Courcelle. In IEEE 51st Annual Symposium on Foundations of Computer Science (FOCS), pages 143-152, 2010. Google Scholar
  23. Amr Elmasry, Torben Hagerup, and Frank Kammer. Space-efficient Basic Graph Algorithms. In International Symposium on Theoretical Aspects of Computer Science (STACS), pages 288-301, 2015. URL: https://doi.org/10.4230/LIPIcs.STACS.2015.288.
  24. Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, Michał Pilipczuk, and Marcin Wrochna. Fully polynomial-time parameterized computations for graphs and matrices of low treewidth. ACM Transactions on Algorithms, 14(3), 2018. Google Scholar
  25. Greg N. Frederickson. Upper bounds for time-space trade-offs in sorting and selection. Journal of Computer and System Sciences, 34(1):19-26, 1987. URL: https://doi.org/10.1016/0022-0000(87)90002-X.
  26. Torben Hagerup. Space-efficient DFS and applications to connectivity problems: Simpler, leaner, faster. Algorithmica, 82(4):1033-1056, 2020. URL: https://doi.org/10.1007/s00453-019-00629-x.
  27. Tatsuya Imai, Kotaro Nakagawa, Aduri Pavan, N. Variyam Vinodchandran, and O. Watanabe. An O(n^1/2 + ε)-space and polynomial-time algorithm for directed planar reachability. In IEEE Conference on Computational Complexity (CCC), pages 277-286, 2013. Google Scholar
  28. Rahul Jain and Raghunath Tewari. An O(n^1/4 + ε) Space and Polynomial Algorithm for Grid Graph Reachability. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), pages 19:1-19:14, 2019. Google Scholar
  29. Rahul Jain and Raghunath Tewari. Reachability in High Treewidth Graphs. In International Symposium on Algorithms and Computation (ISAAC), volume 149, pages 12:1-12:14, 2019. URL: https://doi.org/10.4230/LIPIcs.ISAAC.2019.12.
  30. Frank Kammer, Dieter Kratsch, and Moritz Laudahn. Space-efficient biconnected components and recognition of outerplanar graphs. Algorithmica, 81(3):1180-1204, 2019. URL: https://doi.org/10.1007/s00453-018-0464-z.
  31. Frank Kammer, Johannes Meintrup, and Andrej Sajenko. Space-efficient vertex separators for treewidth. CoRR, abs/1907.00676, 2019. URL: http://arxiv.org/abs/1907.00676.
  32. Frank Kammer and Andrej Sajenko. Linear-time in-place dfs and bfs on the word ram. In International Conference on Algorithms and Complexity (CIAC), pages 286-298, 2019. Google Scholar
  33. Shahbaz Khan and Shashank K. Mehta. Depth First Search in the Semi-streaming Model. In International Symposium on Theoretical Aspects of Computer Science (STACS), volume 126, pages 42:1-42:16, 2019. URL: https://doi.org/10.4230/LIPIcs.STACS.2019.42.
  34. Masashi Kiyomi, Hirotaka Ono, Yota Otachi, Pascal Schweitzer, and Jun Tarui. Space-efficient algorithms for longest increasing subsequence. Theory of Computing Systems, 2019. URL: https://doi.org/10.1007/s00224-018-09908-6.
  35. Tom Leighton and Satish Rao. Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. Journal of the ACM, 46(6):787–832, 1999. URL: https://doi.org/10.1145/331524.331526.
  36. Andrea Lincoln, Virginia Vassilevska Williams, Joshua R. Wang, and R. Ryan Williams. Deterministic Time-Space Trade-Offs for k-SUM. In International Colloquium on Automata, Languages, and Programming (ICALP), volume 55, pages 58:1-58:14, 2016. URL: https://doi.org/10.4230/LIPIcs.ICALP.2016.58.
  37. J.Ian Munro and Mike Paterson. Selection and sorting with limited storage. Theoretical Computer Science, 12(3):315-323, 1980. URL: https://doi.org/10.1016/0304-3975(80)90061-4.
  38. Jakob Pagter and Theis Rauhe. Optimal time-space trade-offs for sorting. In ACM Symposium on Theory of Computer Science (STOC), pages 264-268, 1998. URL: https://doi.org/10.1109/SFCS.1998.743455.
  39. Chung Keung Poon. Space bounds for graph connectivity problems on node-named jags and node-ordered jags. In IEEE 34th Annual Symposium on Foundations of Computer Science (FOCS), page 218–227, 1993. Google Scholar
  40. John H. Reif. Depth-first search is inherently sequential. Information Processing Letters, 20(5):229-234, 1985. URL: https://doi.org/10.1016/0020-0190(85)90024-9.
  41. Omer Reingold. Undirected connectivity in log-space. Journal of the ACM, 55(4), 2008. URL: https://doi.org/10.1145/1391289.1391291.
  42. Joshua R. Wang. Space-efficient randomized algorithms for k-sum. In European Symposium on Algorithms (ESA), pages 810-829, 2014. 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