Space efficient algorithm for solving reachability using tree decomposition and separators

To solve reachability is to determine whether there is a path from one vertex to the other in a graph. Standard graph traversal algorithms such as DFS and BFS take linear time to solve 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 ). In this paper, we study space-efficient algorithms for deciding reachability that runs in polynomial time. We show a polynomial-time algorithm that solves reachability in directed graphs using O ( w log ⁡ n ) space. Our algorithm requires access to a tree decomposition of width w for the underlying undirected graph of the input. This requirement can be waived for graphs for which recursive balanced vertex separators can be computed space-efficiently.

Authors

• Rahul Jain University of Southern California
• Raghunath Tewari

Keywords

• Graph reachability
• Simultaneous time-space upper bound
• Tree decomposition