Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR14-071 | 7th May 2014 00:36

O(sqrt(n))-Space and Polynomial-time Algorithm for the Planar Directed Graph Reachability Problem



We show an O(sqrt(n))-space and polynomial-time algorithm for solving the planar directed graph reachability problem. Imai et al. showed in CCC 2013 that the problem is solvable in O(n^{1/2+eps})-space and polynomial-time by using separators for planar graphs, and it has been open whether the space bound can be improved to a natural bound O(n^{1/2}). Based on the technique using universal sequences, which has been introduced recently by Asano and Kirkpatrick, we solved this question affirmatively. The main technical contribution is to show a space efficient way to define/construct a cycle-separator that can be used in sublinear computation.

ISSN 1433-8092 | Imprint