O(sqrt(n))-Space and Polynomial-time Algorithm for the Planar Directed Graph Reachability Problem.
Tetsuo Asano, David G. Kirkpatrick, Kotaro Nakagawa, Osamu Watanabe · Electronic colloquium on computational complexity · 2014
Throughout this paper we will use n to denote the number of vertices of an input graph, which is the unique input size parameter. For a directed graph G = (V,E), its underlying graph is the undirected graph ‘G = (V, ‘E), where the vertex pair {u, v} belongs to ‘E if and only if at least one of (u, v) or (v, u) belongs to E. The planar directed graph reachability problem is a special case of the reachability problem where we restrict attention to input graphs whose underlying graph is planar. For a simpler setting to introduce some of our algorithmic ideas, we also consider the grid directed graph reachability problem, where we restrict attention to input graphs whose underlying graph is an edge-induced subgraph of a square grid. We will frequently refer to these problems with the shorter names “planar reachability” and “grid reachability.” The directed graph reachability problem is a core problem in computational complexity theory. It is a canonical complete problem for the nondeterministic log-space, NL, and the famous open question L = NL is essentially asking whether the problem is solvable deterministically in logspace. The standard breadth first search algorithm and Savitch’s algorithm are two of the most fundamental algorithms known for solving the directed graph reachability problem. The former has a (roughly) linear space and time implementation, and the latter uses only O((log n)2)-space but requires Θ(nlogn) time. Hence a natural and significant question is whether we can design an algorithm for directed graph reachability that is efficient in both space and time. In particular, can we design a polynomial-time algorithm for the directed graph reachability problem that uses only O(n )-space for some small constant < 1? This question was asked by Wigderson in his excellent survey paper [13], and it remains unsettled. The best known result in this direction is the two decades old bound due to Barns, Buss, Ruzzo and Schieber [4], who showed a polynomial-time algorithm for the problem that uses O(n/2 √ logn) space. Note that this space bound is only slightly sublinear, and improving this bound remains a significant open question. In fact, there are indications that it may be difficult to improve this bound because there are