ECCC-Report TR14-071https://eccc.weizmann.ac.il/report/2014/071Comments and Revisions published for TR14-071en-usFri, 16 May 2014 22:57:48 +0300
Paper TR14-071
| O(sqrt(n))-Space and Polynomial-time Algorithm for the Planar Directed Graph Reachability Problem |
Osamu Watanabe,
Tetsuo Asano,
David Kirkpatrick,
Kotaro Nakagawa
https://eccc.weizmann.ac.il/report/2014/071We 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.Fri, 16 May 2014 22:57:48 +0300https://eccc.weizmann.ac.il/report/2014/071