Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR10-154 | 8th October 2010 23:52

Space-Efficient Algorithms for Reachability in Surface-Embedded Graphs

RSS-Feed

Abstract:

We consider the reachability problem for a certain class of directed acyclic graphs embedded on surfaces. Let {\cal G}(m,g) be the class of directed acyclic graphs with m = m(n) source vertices embedded on a surface (orientable or non-orientable) of genus g = g(n). We give a log-space reduction that on input \langle G,u,v \rangle where G\in {\cal G}(m,g) and u and v are two vertices of G, outputs \langle G',u',v' \rangle where G' is directed graph, and u', v' are vertices of G', so that (a) there is a directed path from u to v in G if and only if there is a directed path from u' to v' in G' and (b) G' has O(m+g) vertices.

By a direct application of Savitch's theorem on the reduced instance we
get a deterministic O(\log n + \log^{2}(m+g))-space algorithm for the reachability problem for graphs in {\cal G}(m,g). By setting m and g to be 2^{O(\sqrt{\log n})} we get that the reachability problem for directed acyclic graphs with 2^{O(\sqrt{\log n})} sources embedded on surfaces of genus 2^{O(\sqrt{\log n})} is in \L (deterministic logarithmic space). Earlier, in this direction, deterministic log-space algorithms were known only for planar directed acyclic graphs with O(\log n) sources. Hence our result drastically improves the class of directed graphs for which we now know how to decide reachability in deterministic logarithmic space. By setting m and g to be n^{o(1)} we get a deterministic algorithm for reachability for directed acyclic graphs embedded on surfaces with sub-polynomial genus and with sub-polynomial number of sources, that asymptotically beats Savitch's O(\log^2 n) space bound.

Our reduction can also be combined with a simple depth-first search to achieve new simultaneous time-space upper bounds for reachability in a large class of directed acyclic graphs embedded on surfaces. In particular, for any \epsilon < 1, by performing a depth-first search on the reduced instance, we get a polynomial time algorithm for reachability over graphs in {\cal G}(O(n^\epsilon),O(n^\epsilon)) that uses O(n^\epsilon) space. This beats the best upper bound of polynomial time and O(n/2^{\sqrt{\log n}}) space for this class of graphs known earlier.



ISSN 1433-8092 | Imprint