I have a lot of difficulties with constructing algorithms that use $O(\log n)$ space, as I am unsure about how much can be stored on the worktape.

I am trying to figure out an algorithm for the problem:

UCYCLE = {<G>|G is an undirected graph that contains a simple cycle}

I can't seem to understand how to create an algorithm in logspace that can solve this problem. In my head, it has to store all the previously visited nodes (since it can't visit the same node twice). Also, I am really stuck on how to start searching, when I can't use non-determinism. Can someone help me with some pointers on how to go forward so I can figure out an algorithm?

(PS: This is not homework, but I need to understand how to create algorithms for problems in L and NL)

  • 2
    $\begingroup$ Loop over each edge, cut it, and use USTCON to check if the two vertices are still connected. $\endgroup$ – Geoffrey Irving May 22 '14 at 20:06
  • $\begingroup$ Hm, I think that solution is a bit above what I am capable of understanding (as I wrote, I am not too good at this yet). But if there is a cycle, doesn't that simply mean that there is a path from s to s? Can i use the same algorithm that I use for PATH, only change it so that it goes from s to s, instead of s to t? I also guess that that it has to be at least 3 steps long. $\endgroup$ – user16655 May 22 '14 at 20:34
  • $\begingroup$ The USTCON algorithm is extremely technical, so if you are a beginner it is going to be difficult to understand. Any algorithm for UCYCLE will have similar complexity (or be a major breakthrough), since the reduction between the two algorithms is my one sentence description above. $\endgroup$ – Geoffrey Irving May 22 '14 at 22:28
  • 3
    $\begingroup$ @Geoffrey: UCYCLE in L is much easier to show than USTCON in L. Indeed, it's an exercise problem in Sipser's textbook (problem 8.23). I'm reluctant to post an answer since this could be a homework problem. $\endgroup$ – Robin Kothari May 23 '14 at 0:55
  • $\begingroup$ Ah, right, I was implicitly thinking of something like USTCYCLE. Apologies for the incorrect comment. $\endgroup$ – Geoffrey Irving May 23 '14 at 1:51

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

Now vou start such a traversal once from every node $v$, remembering only $v$ and the edge you left $v$ through. If the traversal returns to $v$ through a different edge, then $v$ lies on a cycle. If this is not the case for all $v$, then the graph is acyclic.

In general, in a logarithmic space algorithm you can only store constantly many pointers into the input and counters.


Not the answer you're looking for? Browse other questions tagged or ask your own question.