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 ������(log2 ������). 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 ������(������ log ������) space. Our algorithm requires access to a tree decomposition of width ������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.

Automated summary

To solve the reachability problem is to determine if there is a path between two vertices in a graph. This paper studies space-efficient algorithms that run in polynomial time to decide reachability. An algorithm is presented that solves reachability in directed graphs using O(n log n) space.