Solving cycle in undirected graph in log space?

Question

Setting

Let: $$UCYLE = \mathcal \{ <G> ~:~ G \text{ is an undirected graph that contains a simple cycle}\}.$$

My Solution

we show $UCYLE \in L$ by constructing $\mathcal M$ that decides $UCYLE$ using $L$ space.

$\mathcal M = $"On input $<G>$ where $G = (\mathbb V, \mathbb E)$:

1. For each $v_i \in \mathbb V$, for each $v_j \in Neighbor(v_i)$, store the current $v_i$ and $v_j$.

2. Traverse the edge $(v_i,v_j)$ and then follow all possible paths through $G$ using DFS.

3. If we encounter $v_k \in Neighbor(v_i) / \{v_j\}$ so that there is an edge $(v_i,v_k) \in \mathbb E$, then ACCEPT. Else REJECT."

First we claim $\mathcal M$ decides $UCYLE$. First, if there exists a cycle in $G$, then it must start and end on some vertex $v_i$, step one of $\mathcal M$ tries all such $v_i$'s and therefore must find the desired vertex. Next, suppose the cycle starts at $v_i$, then there must exists a starting edge $(v_i,v_j)$ so that if we follow the cycle, we come back to $v_i$ through a different edge $(v_k,v_i)$, so we accept in step three. Since the graph is undirected, we can always come back to $v_i$ through $(v_i,v_j)$, but $\mathcal M$ does not accept this case. By construction, neither does $\mathcal M$ accept if we come upon some $v_k \in Neighbor(v_i)/\{v_j\}$ but there is no edge from $v_k$ to $v_i$.\newline

Now we show $\mathcal M \in L$. First if the vertices are labled $1,\ldots,n$ where $|\mathbb V| = n$, then it requires $log(n)$ bits to specify each $v_i$. Next note in $\mathcal M$ we only need to keep track of the current $v_i$ and $v_j$, so $\mathcal M$ is $2 log(n) = O(log ~n) \in L$.

My Problem

My problem is how do you perform DFS on the graph in $log(n)$ space. For example, in the worst case where each vertex has degree $n$, you'd have to keep a counter of which vertex you took on a particular path, which would require $n \log(n)$ space.

Answer 1

The trick is to use Reingold's result that undirected reachability is in logspace. For each vertex $v$, we check whether the connected component containing $v$ contains a cycle by counting the number of vertices and edges. We do that by going over all vertices $u$, check whether $u$ is reachable from $v$, and if so, increase the vertex counter by 1 and the edge counter by half the degree of $u$. After going over all vertices, we have counted the number of vertices $V$ and edges $E$ in the connected component containing $v$. This component contains a cycle if and only if $E \geq V$.