Document Open Access Logo

Depth-First Search in Directed Planar Graphs, Revisited

Authors Eric Allender , Archit Chauhan, Samir Datta

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2021.7.pdf
  • Filesize: 0.94 MB
  • 22 pages

Document Identifiers

Author Details

Eric Allender
  • Rutgers University, Piscataway, NJ, USA
Archit Chauhan
  • Chennai Mathematical Institute, India
Samir Datta
  • Chennai Mathematical Institute, India

Funding

  • Allender, Eric: Supported in part by NSF Grant CCF-1909216 and CCF-1909683.
  • Chauhan, Archit: Partially supported by a grant from Infosys foundation and TCS PhD fellowship.
  • Datta, Samir: Partially supported by a grant from Infosys foundation and SERB-MATRICS grant MTR/2017/000480.

Cite As Get BibTex

Eric Allender, Archit Chauhan, and Samir Datta. Depth-First Search in Directed Planar Graphs, Revisited. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 7:1-7:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.MFCS.2021.7

Abstract

We present an algorithm for constructing a depth-first search tree in planar digraphs; the algorithm can be implemented in the complexity class AC^1(UL∩co-UL), which is contained in AC². Prior to this (for more than a quarter-century), the fastest uniform deterministic parallel algorithm for this problem was O(log^{10}n) (corresponding to the complexity class AC^{10} ⊆ NC^{11}). 
We also consider the problem of computing depth-first search trees in other classes of graphs, and obtain additional new upper bounds.

Subject Classification

ACM Subject Classification
  • Theory of computation → Complexity classes
  • Theory of computation → Parallel algorithms
Keywords
  • Depth-First Search
  • Planar Digraphs
  • Parallel Algorithms
  • Space-Bounded Complexity Classes

Metrics

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

Related Versions

References

  1. Alok Aggarwal, Richard J. Anderson, and Ming-Yang Kao. Parallel depth-first search in general directed graphs. SIAM J. Comput., 19(2):397-409, 1990. URL: https://doi.org/10.1137/0219025.
  2. 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. URL: https://doi.org/10.1007/s00224-009-9172-z.
  3. Eric Allender, Archit Chauhan, and Samir Datta. Depth-first search in directed graphs, revisited. Technical Report TR20-074, Electronic Colloquium on Computational Complexity (ECCC), 2020. Google Scholar
  4. Eric Allender, Archit Chauhan, Samir Datta, and Anish Mukherjee. Planarity, exclusivity, and unambiguity. Electronic Colloquium on Computational Complexity (ECCC), 26:39, 2019. Google Scholar
  5. Eric Allender, Klaus Reinhardt, and Shiyu Zhou. Isolation, matching, and counting: Uniform and nonuniform upper bounds. Journal of Computer and System Sciences, 59(2):164-181, 1999. Google Scholar
  6. Sanjeev Arora and Boaz Barak. Computational Complexity, a modern approach. Cambridge University Press, 2009. Google Scholar
  7. 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 Hee-Kap Ahn and Chan-Su Shin, editors, Proc. 25th International Symposium on Algorithms and Computation (ISAAC), volume 8889 of Lecture Notes in Computer Science, pages 553-564. Springer, 2014. URL: https://doi.org/10.1007/978-3-319-13075-0_44.
  8. Chris Bourke, Raghunath Tewari, and N. V. Vinodchandran. Directed planar reachability is in unambiguous log-space. TOCT, 1(1):4:1-4:17, 2009. URL: https://doi.org/10.1145/1490270.1490274.
  9. Samir Datta, Nutan Limaye, Prajakta Nimbhorkar, Thomas Thierauf, and Fabian Wagner. Planar graph isomorphism is in log-space. In Proceedings of the 24th Annual IEEE Conference on Computational Complexity (CCC), pages 203-214, 2009. URL: https://doi.org/10.1109/CCC.2009.16.
  10. Pilar de la Torre and Clyde P. Kruskal. Fast parallel algorithms for all-sources lexicographic search and path-algebra problems. J. Algorithms, 19(1):1-24, 1995. URL: https://doi.org/10.1006/jagm.1995.1025.
  11. Pilar de la Torre and Clyde P. Kruskal. Polynomially improved efficiency for fast parallel single-source lexicographic depth-first search, breadth-first search, and topological-first search. Theory Comput. Syst., 34(4):275-298, 2001. URL: https://doi.org/10.1007/s00224-001-1008-4.
  12. Reinhard Diestel. Graph Theory, volume 173 of Graduate texts in mathematics. Springer, 2016. Google Scholar
  13. Amr Elmasry, Torben Hagerup, and Frank Kammer. Space-efficient basic graph algorithms. In Proc. 32nd International Symposium on Theoretical Aspects of Computer Science (STACS), volume 30 of LIPIcs, pages 288-301. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015. URL: https://doi.org/10.4230/LIPIcs.STACS.2015.288.
  14. Torben Hagerup. Planar depth-first search in O(log n) parallel time. SIAM J. Comput., 19(4):678-704, 1990. URL: https://doi.org/10.1137/0219047.
  15. 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.
  16. Taisuke Izumi and Yota Otachi. Sublinear-space lexicographic depth-first search for bounded treewidth graphs and planar graphs. In Proc. 47th International Colloquium on Automata, Languages and Programming (ICALP), LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. to appear. Google Scholar
  17. B. Jenner and B. Kirsig. Alternierung und Logarithmischer Platz. Dissertation, Universität Hamburg, 1989. Google Scholar
  18. Ming-Yang Kao and Philip N. Klein. Towards overcoming the transitive-closure bottleneck: Efficient parallel algorithms for planar digraphs. Journal of Computer and System Sciences, 47(3):459-500, 1993. URL: https://doi.org/10.1016/0022-0000(93)90042-U.
  19. Maxim Naumov, Alysson Vrielink, and Michael Garland. Parallel depth-first search for directed acyclic graphs. In Proc. 7th Workshop on Irregular Applications: Architectures and Algorithms, pages 4:1-4:8, 2017. URL: https://doi.org/10.1145/3149704.3149764.
  20. John H. Reif. Depth-first search is inherently sequential. Inf. Process. Lett., 20(5):229-234, 1985. URL: https://doi.org/10.1016/0020-0190(85)90024-9.
  21. Omer Reingold. Undirected connectivity in log-space. J. ACM, 55(4), 2008. Google Scholar
  22. Klaus Reinhardt and Eric Allender. Making nondeterminism unambiguous. SIAM J. Comput., 29(4):1118-1131, 2000. URL: https://doi.org/10.1137/S0097539798339041.
  23. Raghunath Tewari and N. V. Vinodchandran. Green’s theorem and isolation in planar graphs. Inf. Comput., 215:1-7, 2012. URL: https://doi.org/10.1016/j.ic.2012.03.002.
  24. Thomas Thierauf and Fabian Wagner. The isomorphism problem for planar 3-connected graphs is in unambiguous logspace. Theory Comput. Syst., 47(3):655-673, 2010. URL: https://doi.org/10.1007/s00224-009-9188-4.
  25. W. T. Tutte. Separation of vertices by a circuit. Discrete Mathematics, 12(2):173-184, 1975. Google Scholar
  26. H. Vollmer. Introduction to Circuit Complexity: A Uniform Approach. Springer-Verlag New York Inc., 1999. URL: https://doi.org/10.1007/978-3-662-03927-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 About DROPS Imprint Privacy Contact