A fast randomized LOGSPACE algorithm for graph connectivity

We study the relationship between undirected graph reachability and graph connectivity, in the context of randomized LOGSPACE algorithms. Aleluinas et al. [2] show that graph reachability (checking whether there is a path connecting vertices J and ℸ) can be decided in logarithmic space and polynomial time, by starting a random walk at J, and checking whether ℸ is hit within some time limit. The randomized algorithm has one-sided error (with small probability, it fails to determine that J and ℸ are connected). The reachability algorithm may be used in order to decide (with one-sided error) whether a graph is connected, by running it n − 1 times, each time with a different target vertex ℸ. This increases the running time by a factor of n. In this paper we give an alternative randomized LOGSPACE algorithm for graph connectivity. Its running time varies between O(n 2) steps and O(n 3) steps, depending on the structure of the input graph. This matches the fastest known RLOGSPACE algorithm for reachability, up to a constant factor. Our algorithm has two-sided error.

Authors

• Uriel Feige

Keywords

No keywords are indexed for this paper.