Document Open Access Logo

Reachability in High Treewidth Graphs

Authors Rahul Jain , Raghunath Tewari

PDF

File

Thumbnail PDF
PDF
LIPIcs.ISAAC.2019.12.pdf
  • Filesize: 0.54 MB
  • 14 pages

Document Identifiers

Subject Classification

ACM Subject Classification
  • Theory of computation
Keywords
  • graph reachability
  • simultaneous time-space upper bound
  • tree decomposition

Metrics

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

Abstract

Reachability is the problem of deciding whether there is a path from one vertex to the other in the graph. Standard graph traversal algorithms such as DFS and BFS take linear time to decide reachability; however, their space complexity is also linear. On the other hand, Savitch’s algorithm takes quasipolynomial time although the space bound is O(log^2 n). Here, we study space efficient algorithms for deciding reachability that run in polynomial time. 
In this paper, we show that given an n vertex directed graph of treewidth w along with its tree decomposition, there exists an algorithm running in polynomial time and O(w log n) space that solves the reachability problem.

Cite As Get BibTex

Rahul Jain and Raghunath Tewari. Reachability in High Treewidth Graphs. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 12:1-12:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.ISAAC.2019.12

Author Details

Rahul Jain
  • Indian Institute of Technology Kanpur, India
Raghunath Tewari
  • Indian Institute of Technology Kanpur, India

Funding

  • Jain, Rahul: Ministry of Human Resource Development, Government of India
  • Tewari, Raghunath: DST Inspire Faculty Grant, Visvesvaraya Young Faculty Fellowship

References

  1. Noga Alon, Paul Seymour, and Robin Thomas. A separator theorem for nonplanar graphs. Journal of the American Mathematical Society, 3(4):801-808, 1990. Google Scholar
  2. Stefan Arnborg, Derek G. Corneil, and Andrzej Proskurowski. Complexity of Finding Embeddings in a k-Tree. SIAM Journal on Algebraic Discrete Methods, 8(2):277-284, 1987. Google Scholar
  3. Stefan Arnborg and Andrzej Proskurowski. Linear time algorithms for NP-hard problems restricted to partial k-trees. Discrete applied mathematics, 23(1):11-24, 1989. Google Scholar
  4. Tetsuo Asano and Benjamin Doerr. Memory-Constrained Algorithms for Shortest Path Problem. In Proceedings of the 23rd Annual Canadian Conference on Computational Geometry (CCCG 2011), 2011. Google Scholar
  5. Tetsuo Asano, David Kirkpatrick, Kotaro Nakagawa, and Osamu Watanabe. Õ(√n)-Space and Polynomial-Time Algorithm for Planar Directed Graph Reachability. In Proceedings of the 39th International Symposium on Mathematical Foundations of Computer Science (MFCS 2014), pages 45-56, 2014. Google Scholar
  6. 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. Google Scholar
  7. Hans L. Bodlaender and Arie M. C. A. Koster. Combinatorial Optimization on Graphs of Bounded Treewidth. The Computer Journal, 51(3):255-269, 2008. Google Scholar
  8. Diptarka Chakraborty, Aduri Pavan, Raghunath Tewari, N. V. Vinodchandran, and Lin F. Yang. New Time-Space Upperbounds for Directed Reachability in High-genus and H-minor-free Graphs. In Proceedings of the 34th Annual Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014), pages 585-595, 2014. Google Scholar
  9. 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 (TOCT), 9(4):19:1-19:11, 2017. Google Scholar
  10. Bireswar Das, Samir Datta, and Prajakta Nimbhorkar. Log-Space Algorithms for Paths and Matchings in k-Trees. Theory of Computing Systems, 53(4):669-689, 2013. Google Scholar
  11. Michael Elberfeld, Andreas Jakoby, and Till Tantau. Logspace Versions of the Theorems of Bodlaender and Courcelle. In Proceedings of the 51st Annual Symposium on Foundations of Computer Science (FOCS 2010), pages 143-152. IEEE Computer Society, 2010. Google Scholar
  12. Uriel Feige, MohammadTaghi Hajiaghayi, and James R. Lee. Improved Approximation Algorithms for Minimum Weight Vertex Separators. SIAM Journal on Computing, 38(2):629-657, 2008. Google Scholar
  13. J. Gilbert, D. Rose, and A. Edenbrandt. A Separator Theorem for Chordal Graphs. SIAM Journal on Algebraic Discrete Methods, 5(3):306-313, 1984. Google Scholar
  14. Tatsuya Imai, Kotaro Nakagawa, Aduri Pavan, N. V. Vinodchandran, and Osamu Watanabe. An O(n^1/2 + ε)-Space and Polynomial-Time Algorithm for Directed Planar Reachability. In Proceedings of the 28th Conference on Computational Complexity, CCC 2013, pages 277-286, 2013. Google Scholar
  15. Andreas Jakoby and Till Tantau. Logspace Algorithms for Computing Shortest and Longest Paths in Series-Parallel Graphs. In Proceedings of the 27th Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2007), pages 216-227, 2007. Google Scholar
  16. Ken-ichi Kawarabayashi and Bruce Reed. A separator theorem in minor-closed classes. In Proceedings of the 51st Annual Symposium on Foundations of Computer Science (FOCS 2010), pages 153-162. IEEE, 2010. Google Scholar
  17. Omer Reingold. Undirected connectivity in log-space. Journal of the ACM (JACM), 55(4):17, 2008. Google Scholar
  18. Walter J Savitch. Relationships between nondeterministic and deterministic tape complexities. Journal of Computer and System Sciences, 4(2):177-192, 1970. Google Scholar
  19. Avi Wigderson. The complexity of graph connectivity. In Proceedings of the 17th International Symposium on Mathematical Foundations of Computer Science (MFCS 1992), pages 112-132. Springer, 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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact