ECCC-Report TR09-049https://eccc.weizmann.ac.il/report/2009/049Comments and Revisions published for TR09-049en-usFri, 05 Jun 2009 01:54:39 +0300
Paper TR09-049
| A log-space algorithm for reachability in planar DAGs with few sources |
Derrick Stolee,
Chris Bourke,
N. V. Vinodchandran
https://eccc.weizmann.ac.il/report/2009/049Designing algorithms that use logarithmic space for graph reachability problems is fundamental to complexity theory. It is well known that for general directed graphs this problem is equivalent to the NL vs L problem. For planar graphs, the question is not settled. Showing that the planar reachability problem is NL-complete would show that nondeterministic log-space computations can be made unambiguous. On the other hand, very little is known about classes of planar graphs that admit log-space algorithms. We make progress in this direction. We show that reachability in planar DAGs with O(log n) number of sources can be solved in log-space. We use a new decomposition technique for planar DAGs as a basis for our algorithm.
Fri, 05 Jun 2009 01:54:39 +0300https://eccc.weizmann.ac.il/report/2009/049