$UCYCLE$ is in $L$

I'm trying to understand the log-space algorithm for $$UCYCLE = \{ \langle G \rangle \ | \text{ $G$ is an undirected graph containing a cycle} \}$$

The basic idea is traversing from every $v\in V$, remembering the first edge and checking if we got back to $v$ from another edge.

What I don't quite understand is the way of traversing; This answer says:


For the undirected cycle problem, you can traverse each connected
component: at each node, when coming in through edge $k$, leave through
edge $k+1$. (We can assume edges are ordered at each vertex.)

I don't quite understand it - after exhausting all the edges of the form $\langle v,u_i \rangle$ where do we go from here? I could of course remembering what edge brought us to $v$ but then we clearly exceed the $O(\log n)$ boundary.

First of all, let me give the correct attribution to this algorithm: Cook and McKenzie, Problems complete for deterministic logarithmic space.

The setup of Cook and McKenzie is that you are given an undirected graph in which the edges incident to a vertex $v$ are ordered (cyclically), and given one of them it is possible to find the next one in the order.

Consider now the following algorithm, for an vertex $v$ and an incident edge $e$:

• Set $v_0 = v$ and $e_0 = e$.

• Let $v'$ be the other endpoint of $e$. Set $v = v'$.

• Repeat:

-

• Let $e'$ be the edge following $e$ in the cyclic order of $v$.

-

• Let $v'$ be the other endpoint of $e'$.

-

• Replace $v,e$ by $v',e'$.

• Until $v = v_0$.

• If $e \neq e_0$, return "cyclic", otherwise return "don't know".

We now have two claims:

• If $G$ is acyclic then the algorithm returns "don't know" whatever $v,e$ we start with.

• If $G$ is cyclic then there is a choice of $v,e$ for which the algorithm returns "cyclic".

To see the first claim, suppose that $G$ is acyclic, and let $v,e$ be given. Consider the connected component containing $v$. If we remove $e$ then it breaks into two connected components $C_1,C_2$, the first containing $v$, the other not containing $v$. At the first step of the algorithm, it moves to $C_2$. The only way to return to $C_1$ is via the edge $e$, and when that happens, the algorithm will return "don't know".

To see the second claim, suppose that $G$ contains some cycle $v_1,\ldots,v_\ell$, and suppose for the sake of contradiction that whenever running the algorithm with $v,e$ it outputs "don't know". Let us run the algorithm with $v=v_1$ and $e=(v_1,v_2)$. Let the edges incident to $v_2$ be $e,e_1,\ldots,e_t$. According to the assumption, the algorithm will take the edge $e_1$, get back to $v_2$ via $e_1$, traverse $e_2$, get back to $v_2$ via $e_2$, and so on. In particular, it will reach $(v_2,v_3)$ before reaching $e$. By assumption, the only way to go back to $v_1$ is via $e$, and so the algorithm will reach $v_3$ before it goes back to $v_1$.

Let the edges incident to $v_3$ be $(v_3,v_2),e'_1,\ldots,e'_s$. As before, the walk will traverse $e'_1$, go back to $v_3$ via $e'_1$, traverse $e'_2$, go back to $v_3$ via $e'_2$, and so on. In particular, it will reach $(v_3,v_4)$ before reaching $(v_3,v_2)$. Now, by assumption $(v_3,v_2)$ is the only way to get back to $v_2$, which is the only way to get back to $v_1$. Therefore the algorithm will reach $(v_3,v_4)$ before it goes back to $v_1$.

Continuing in this way, we see that the algorithm will traverse $(v_4,v_5),\ldots,(v_\ell,v_1)$, and the last edge will be the first time at which it gets back to $v_1$. We reach a contradiction since $(v_\ell,v_1) \neq (v_2,v_1)$.

StackExchange Computer Science Q#81148, answer score: 7