2026-08-03T00:52:05Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11508 2024-03-06T10:48:11Z ddc:004 open_access

Reachability in High Treewidth Graphs Jain, Rahul Tewari, Raghunath graph reachability simultaneous time-space upper bound tree decomposition 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Rahul Jain and Raghunath Tewari 2019 Is Part Of LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2019.12 urn:nbn:de:0030-drops-115087 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.12 eng https://creativecommons.org/licenses/by/3.0/legalcode