TR14-071 Authors: Tetsuo Asano, David Kirkpatrick, Kotaro Nakagawa, Osamu Watanabe

Publication: 16th May 2014 22:57

Downloads: 1336

Keywords:

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.