Discrete Math Seminar Spring 2009
Log-space algorithm for reachability problem in planar DAGs
with few sources
Derrick Stolee, UNL;
Jan 27
Designing 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 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.
The first talk will cover existing algorithms for reachability in
restricted classes of planar graphs and define the decomposition
technique. The second talk will present the new algorithm and prove
its correctness.
Joint work with Chris Bourke and N.V. Vinodchandran.