A FAST RANDOMIZED LOGSPACE ALGORITHM FOR GRAPH CONNECTIVITY

We study the relationship between undirected graph reachability and gr aph connectivity, in the context of randomized LOGSPACE algorithms. Al eluinas et al. [2] show that graph reachability (checking whether ther e is a path connecting vertices L and F) can be decided in logarithmic space and polynomial time, by starting a random walk at L, and checki ng whether F is hit within some time limit. The randomized algorithm h as one-sided error (with small probability, it fails to determine that L and F are connected). The reachability algorithm may be used in ord er to decide (with one-sided error) whether a graph is connected, by r unning it n - 1 times, each time with a different target vertex F. Thi s increases the running time by a factor of n. In this paper we give a n alternative randomized LOGSPACE algorithm for graph connectivity. It s running time varies between O(n(2)) steps and O(n(3)) steps, dependi ng on the structure of the input graph. This matches the fastest known RLOGSPACE algorithm for reachability, up to a constant factor. Our al gorithm has two-sided error.