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?


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!).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.