# $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.

• I don't think this algorithm is guaranteed to traverse the entire connected component (unless it's acyclic). Otherwise, you would get a very simple algorithm for undirected reachability in logspace (such an algorithm, due to Reingold, is known, but it is significantly more complicated). – Yuval Filmus Sep 12 '17 at 14:28

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:

1. If $$G$$ is acyclic then the algorithm returns "don't know" whatever $$v,e$$ we start with.
2. 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)$$.

• Thanks so much for the detailed analysis. Very impressive result! – Covvar Sep 12 '17 at 14:50
• I believe that after "Set $v_0 = v$ and $e_0 = e$", there should be another step "Let $v'$ be the other endpoint of $e$. Set $v = v'$". This is needed because we want $e_0$ in $(v_0, e_0)$ to be an 'outgoing' edge, but in subsequent $(v, e)$, we want $e$ to be an 'incoming' edge to $v$. Even though this is an undirected graph, the proof needs this distinction, as otherwise you will reach $v_0$ via $e_0$, but the pair that you'll be considering at that point be $(v', e_0)$ and not $(v_0, e_0)$, and if $deg(v_0) > 1$, in the next step, you'll return "cyclic", even if it is actually acyclic. – CodeChef Apr 10 '20 at 3:43
• How to prove that the traversal algorithm always halt? – Macrophage Nov 30 '20 at 2:22
• This should follow from the current argument. Either you find a cycle, or you eventually return to the origin. – Yuval Filmus Nov 30 '20 at 4:29