Cheap and Secure Web Hosting Provider : See Now

[Solved]: Logspace algorithm for s-t connectivity in undirected forests

, , No Comments
Problem Detail: 

It has been shown that the decision problem
$\{(G, s, t)~\mid~ G\text{ is an undirected forest and there is a path from }s \text{ to } t \}$ is complete for logspace (and therefore in $L$).
But the proof involves a series of reductions which didn't seem very intuitive to me.
Is there any natural algorithm that directly solves this problem in log space?

Asked By : skankhunt42

Answered By : Yuval Filmus

This is proved by Cook and McKenzie. We make use of the following notation:

  1. $\deg(v)$ is the degree of a vertex $v$.

  2. $N(v,1),\ldots,N(v,\deg(v))$ is some fixed ordering of the neighbors of $v$.

We construct a sequence $v_1,v_2,\ldots$ of nodes starting with $v_1 = s$ and $v_2 = N(s,1)$ (if $\deg(s) = 0$ then $s$ is connected to $t$ iff $s = t$). Given $v_{i-2},v_{i-1}$, we construct $v_i$ as follows:

Suppose that $v_{i-2} = N(v_{i-1},j)$. Then $v_i = N(v_{i-1},j+1)$.

(If $j = \deg(v_{i-1})$ then $j+1 = 1$.)

It turns out that if the connected component of $s$ has size $m$ then the first $2(m-1)$ vertices contain each vertex $v$ in the connected component exactly $\deg(v)$ times, and after that the sequence repeats indefinitely. This is because the sequence essentially performs a depth-first search, as the following image from Wikipedia illustrates (the arrows should be ignored):

Tree traversal

Here $s = F$ and the neighbors are ordered from left to right. The first 16 elements of the sequence are F,B,A,B,D,C,D,E,D,B,F,G,I,H,I,G. The sequence then repeats.

This implies the following simple algorithm: calculate the first $2(n-1)$ members of the sequence, and check whether $t$ ever appears. This can be implemented in logarithmic space.

Reingold gave a (significantly) more complicated algorithm that works for any undirected graph, still using only logarithmic space. If the graph is directed then the problem is complete for NL, and so probably cannot be solved using only logarithmic space (at least not on deterministic Turing machines!).

Best Answer from StackOverflow

Question Source :

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback