Document Open Access Logo

New Time-Space Upperbounds for Directed Reachability in High-genus and H-minor-free Graphs

Authors Diptarka Chakraborty, A. Pavan, Raghunath Tewari, N. V. Vinodchandran, Lin Forrest Yang

PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2014.585.pdf
  • Filesize: 468 kB
  • 11 pages

Document Identifiers

Author Details

Diptarka Chakraborty
A. Pavan
Raghunath Tewari
N. V. Vinodchandran
Lin Forrest Yang

Cite As Get BibTex

Diptarka Chakraborty, A. Pavan, Raghunath Tewari, N. V. Vinodchandran, and Lin Forrest Yang. New Time-Space Upperbounds for Directed Reachability in High-genus and H-minor-free Graphs. In 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 29, pp. 585-595, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014) https://doi.org/10.4230/LIPIcs.FSTTCS.2014.585

Abstract

We obtain the following new simultaneous time-space upper bounds for the directed reachability problem. (1) A polynomial-time, O(n^{2/3} * g^{1/3})-space algorithm for directed graphs embedded on orientable surfaces of genus g. (2) A polynomial-time, O(n^{2/3})-space algorithm for all H-minor-free graphs given the tree decomposition, and (3) for K_{3,3}-free and K_5-free graphs, a polynomial-time, O(n^{1/2 + epsilon})-space algorithm, for every epsilon > 0.

For the general directed reachability problem, the best known simultaneous time-space upper bound is the BBRS bound, due to  Barnes, Buss, Ruzzo, and Schieber,  which achieves a space bound of O(n/2^{k * sqrt(log(n))}) with polynomial running time, for any constant k. It is a significant open question to improve this bound for reachability over general directed graphs. Our algorithms beat the BBRS bound for graphs embedded on surfaces of genus n/2^{omega(sqrt(log(n))}, and for all H-minor-free graphs. This significantly broadens the class of directed graphs for which the BBRS bound can be improved.

Subject Classification

Keywords
  • Reachability
  • Space complexity
  • Time-Space Efficient Algorithms
  • Graphs on Surfaces
  • Minor Free Graphs
  • Savitch's Algorithm
  • BBRS Bound

Metrics

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

References

  1. Tetsuo Asano and Benjamin Doerr. Memory-constrained algorithms for shortest path problem. In CCCG, 2011. Google Scholar
  2. Greg Barnes, Jonathan F. Buss, Walter L. Ruzzo, and Baruch Schieber. A sublinear space, polynomial time algorithm for directed s-t connectivity. In Proceedings of the Seventh Annual Structure in Complexity Theory Conference, pages 27-33, 1992. Google Scholar
  3. David A. Mix Barrington. Bounded-width polynomial-size branching programs recognize exactly those languages in \NC¹. Journal of Computer and System Sciences, 38:150-164, 1989. Google Scholar
  4. Chris Bourke, Raghunath Tewari, and N. V. Vinodchandran. Directed planar reachability is in unambiguous log-space. ACM Transactions on Computation Theory, 1(1):1-17, 2009. Google Scholar
  5. Stephen A. Cook and Charles Rackoff. Space lower bounds for maze threadability on restricted machines. SIAM J. Comput., 9(3):636-652, 1980. Google Scholar
  6. Samir Datta, Nutan Limaye, Prajakta Nimbhorkar, Thomas Thierauf, and Fabian Wagner. Planar graph isomorphism is in log-space. In Annual IEEE Conference on Computational Complexity, pages 203-214, 2009. Google Scholar
  7. Samir Datta, Prajakta Nimbhorkar, Thomas Thierauf, and Fabian Wagner. Graph isomorphism for K_3, 3-free and K₅-free graphs is in log-space. In FSTTCS, pages 145-156, 2009. Google Scholar
  8. Hristo Djidjev and Shankar M. Venkatesan. Planarization of graphs embedded on surfaces. In Workshop on Graph Theoretic Concepts in Computer Science, pages 62-72, 1995. Google Scholar
  9. Jeff Edmonds, Chung Keung Poon, and Dimitris Achlioptas. Tight lower bounds for st-connectivity on the NNJAG model. SIAM J. Comput., 28(6), 1999. Google Scholar
  10. John R. Gilbert, Joan P. Hutchinson, and Robert Endre Tarjan. A separator theorem for graphs of bounded genus. J. Algorithms, 5(3):391-407, 1984. Google Scholar
  11. Joan P. Hutchinson and Gary L. Miller. Deleting vertices to make graphs of positive genus planar. Discrete Algorithms and Complexity Theory, 1986. Google Scholar
  12. T. Imai, K. Nakagawa, A. Pavan, N. V. 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
  13. Gary L. Miller and Joseph Naor. Flow in planar graphs with multiple sources and sinks. SIAM Journal on Computing, 24:1002-1017, 1995. Google Scholar
  14. Bojan Mohar and Carsten Thomassen. Graphs on surfaces. 2001. Johns Hopkins Stud. Math. Sci, 2001. Google Scholar
  15. Chung Keung Poon. Space bounds for graph connectivity problems on node-named jags and node-ordered jags. In FOCS, pages 218-227, 1993. Google Scholar
  16. Omer Reingold. Undirected connectivity in log-space. Journal of the ACM, 55(4), 2008. Google Scholar
  17. Omer Reingold, Luca Trevisan, and Salil Vadhan. Pseudorandom walks on regular digraphs and the RL vs. L problem. In STOC'06: Proceedings of the thirty-eighth annual ACM Symposium on Theory of Computing, pages 457-466, New York, NY, USA, 2006. ACM. Google Scholar
  18. Neil Robertson and P. D. Seymour. Graph minors. xvi. excluding a non-planar graph. J. Comb. Theory Ser. B, 89(1):43-76, September 2003. Google Scholar
  19. Walter J. Savitch. Relationships between nondeterministic and deterministic tape complexities. J. Comput. Syst. Sci., 4:177-192, 1970. Google Scholar
  20. Derrick Stolee and N. V. Vinodchandran. Space-efficient algorithms for reachability in surface-embedded graphs. In IEEE Conference on Computational Complexity (CCC), pages 326-333, 2012. Google Scholar
  21. Thomas Thierauf and Fabian Wagner. Reachability in K_3,3-free Graphs and K₅-free Graphs is in Unambiguous Log-Space. In 17th International Conference on Foundations of Computation Theory (FCT), Lecture Notes in Computer Science 5699, pages 323-334. Springer-Verlag, 2009. Google Scholar
  22. N. V. Vinodchandran. Space complexity of the directed reachability problem over surface-embedded graphs. Technical Report TR14-008, ECCC, 2014. Google Scholar
  23. K. Wagner. Über eine Eigenschaft der ebenen Komplexe. Mathematische Annalen, 114(1):570-590, 1937. Google Scholar
  24. Avi Wigderson. The complexity of graph connectivity. Mathematical Foundations of Computer Science 1992, pages 112-132, 1992. 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