随机算法 (Fall 2011)/Graph Connectivity

USTCON stands for undirected [math]\displaystyle{ s }[/math]-[math]\displaystyle{ t }[/math] connectivity. It is the problem which asks whether there is a path from vertex [math]\displaystyle{ s }[/math] to vertex [math]\displaystyle{ t }[/math] in a given undirected graph [math]\displaystyle{ G(V,E) }[/math]. This problem is an abstraction of various search problems in graphs, and has theoretical significance in complexity theory.

The problem can be solved deterministically by traversing the graph [math]\displaystyle{ G(V,E) }[/math], which takes [math]\displaystyle{ \Omega(n) }[/math] extra space to keep track of which vertices have been visited, where [math]\displaystyle{ n=|V| }[/math]. And the following theorem is implied by the upper bound on the cover time.

Theorem (Aleliunas-Karp-Lipton-Lovász-Rackoff 1979)

USTCON can be solved by a polynomial time Monte Carlo randomized algorithm with bounded one-sided error, which uses [math]\displaystyle{ O(\log n) }[/math] extra space.

The algorithm is a random walk starting at [math]\displaystyle{ s }[/math]. If the walk reaches [math]\displaystyle{ t }[/math] in [math]\displaystyle{ 4n^3 }[/math] steps, then return "yes", otherwise return "no".

It is obvious that if [math]\displaystyle{ s }[/math] and [math]\displaystyle{ t }[/math] are disconnected, the random walk from [math]\displaystyle{ s }[/math] can never reach [math]\displaystyle{ t }[/math], thus the algorithm always returns "no".

We know that for an undirected [math]\displaystyle{ G }[/math], the cover time is [math]\displaystyle{ \lt 4nm\lt 2n^3 }[/math]. So if [math]\displaystyle{ s }[/math] and [math]\displaystyle{ t }[/math] are connected, the expected time to reach [math]\displaystyle{ t }[/math] from [math]\displaystyle{ s }[/math] is [math]\displaystyle{ \lt 2n^3 }[/math]. By Markov's inequality, the probability that it takes longer than [math]\displaystyle{ 4n^3 }[/math] steps to reach [math]\displaystyle{ t }[/math] from [math]\displaystyle{ s }[/math] is [math]\displaystyle{ \lt 1/2 }[/math].

The random walk use [math]\displaystyle{ O(\log n) }[/math] bits to store the current position, and another [math]\displaystyle{ O(\log n) }[/math] bits to count the number of steps. So the total space used by the algorithm inaddition to the input is [math]\displaystyle{ O(\log n) }[/math].

This shows that USTCON is in the complexity class RL (randomized log-space).

Story in complexity theory

If the randomness is forbidden, it is known that USTCON can be solved nondeterministically in logarithmic space, thus USTCON is in NL. In fact USTCON is complete for the symmetric version of nondeterministic log-space. That is, every problem in the class of SL can be solved by USTCON via log-space reductions. Therefore, USTCON[math]\displaystyle{ \in }[/math]RL implies that SL[math]\displaystyle{ \subseteq }[/math]RL.

In 2004, Reingold shows that USTCON can be solved deterministically in log-space, which proves SL=L. The deterministic algorithm for USTCON is by the derandomization of random walk.

It is conjectured that RL=L, but this is still open.