5
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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). $\endgroup$ – Yuval Filmus Sep 12 '17 at 14:28
6
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks so much for the detailed analysis. Very impressive result! $\endgroup$ – Covvar Sep 12 '17 at 14:50
  • 1
    $\begingroup$ 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. $\endgroup$ – CodeChef Apr 10 at 3:43
  • $\begingroup$ How to prove that the traversal algorithm always halt? $\endgroup$ – Macrophage Nov 30 at 2:22
  • $\begingroup$ This should follow from the current argument. Either you find a cycle, or you eventually return to the origin. $\endgroup$ – Yuval Filmus Nov 30 at 4:29

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.