2
$\begingroup$

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!

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Covvar May 27 '17 at 15:44
  • $\begingroup$ Yes, this certainly requires proof, though the proof is by reduction to USTCONN. You also need to prove that the criterion for having no cycles is correct. $\endgroup$ – Yuval Filmus May 27 '17 at 15:45
  • $\begingroup$ How can I make the reduction to $USTCONN$? just run $USTCONN(s,s)$ with amplification plus remembering the first edge? $\endgroup$ – Covvar May 29 '17 at 13:06
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus May 29 '17 at 13:08
  • $\begingroup$ 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) $\endgroup$ – Covvar May 29 '17 at 13:17

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.