# detecting a cycle in an undirected graph problem is in $RL$ complexity class

I need come up with an algorithm for detecting a cycle in an undirected graph where the algorithm is in $RL$. That is, the algorithm detects a cycle with a probability greater-equal to $\frac{1}{2}$ but it doesn't return true for a graph with no cycle (no false-positive).

In class, we've learned that $USTCONN$ (the problem of telling if there's a path from $s$ to $t$ in an unidrected graph) is in $RL$.

I thought about utilizing it for the current problem:

1. We choose $s,t$ in random s.t $t$ has at least $2$ edges and check if there's a path between them.
2. Then, in the same fashion, we check if there's a path between $s$ and $t$'s neighbors (If there are too many we may limit it to some constant, randomly, since we must use only logarithmic space)
3. If we found two different paths from $s$ to $u_1,u_2$ where the latter are $t$'s neighbors then there must be two different paths from $s$ to $t$ - Which is a cycle.
4. We repeat the above sufficiently many times (TBD)

I would like to know if that is the algorithm expected from me to come up with before I put efforts in proving that this algorithm is indeed in $RL$.

Thanks!

In fact USTCONN is in L (as shown by Reingold), and you can reduce your problem to USTCONN using non-backtracking walks. These are walks which are not allowed to backtrack, that is, after going from $x$ to $y$ we can't go immediately back to $x$ (but we could go back to $x$ via a different route). The graph contains a cycle iff there is a non-backtracking walk from some vertex to itself. You can formulate this problem as aan undirected connectivity problem, and solve it using the logspace algorithm for USTCONN. As a result, you can detect whether the graph contains a cycle in logspace.
• We did mention that $USTCONN\in L$ but haven't proved that so I guess I shall stick with the fact that $USTCONN \in RL$. Also, I guess some explanation will be needed to claim that $USTCONN$ without backtracing is still in $RL$, right? – Covvar May 27 '17 at 15:44
• How can I make the reduction to $USTCONN$? just run $USTCONN(s,s)$ with amplification plus remembering the first edge? – Covvar May 29 '17 at 13:06
• The proof is by reduction to USTCONN. You implicitly construct a graph (or several graphs), and then apply USTCONN. To implicitly construct a graph $G$, you need to be able to list the vertices of $G$, and given two vertices $x,y$, to determine whether they are connected; all in logspace. – Yuval Filmus May 29 '17 at 13:08
• Few questions: (1) How can I construct a graph $G$ in logspace and what is it used for? (2) Does the proof show that $USTCONN-NOBACKTRACK$ can be reduced to $USTCONN$? (got a little confused) – Covvar May 29 '17 at 13:17