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

<p>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. </p>

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

CC BY-SA 3.0
2014-05-23T07:42:41.240Z
2014-05-23T07:42:41.240Z
Jan Johannsen
<p>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. </p>

<p>I am trying to figure out an algorithm for the problem:</p>

<pre><code>UCYCLE = {&lt;G&gt;|G is an undirected graph that contains a simple cycle}
</code></pre>

<p>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? </p>

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

CC BY-SA 3.0
2014-05-22T20:06:41.820Z
Loop over each edge, cut it, and use USTCON to check if the two vertices are still connected.
Geoffrey Irving
CC BY-SA 3.0
2014-05-22T20:34:18.367Z
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.
user16655
CC BY-SA 3.0
2014-05-22T22:28:56.077Z
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.
Geoffrey Irving
CC BY-SA 3.0
2014-05-23T00:55:20.970Z
@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.
Robin Kothari
CC BY-SA 3.0
2014-05-23T01:51:15.713Z
Ah, right, I was implicitly thinking of something like USTCYCLE.  Apologies for the incorrect comment.
Geoffrey Irving
CC BY-SA 3.0
2014-05-23T07:48:08.237Z
This is a standard textbook exercise, not a research-level problem so it is [off-topic, here](http://cstheory.stackexchange.com/help/on-topic).
David Richerby
CC BY-SA 3.0
2014-05-23T07:56:16.777Z
Just to specify, this is not homework :) I'm studying for my exams, and I'm having some difficulty with the logarithmic space classes.
user16655
<logspace>
Detecting undirected cycles in logarithmic space
user16655
# Detecting undirected cycles in logarithmic space

(Asked by: username_0 on 2014-05-22)

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

**Tags:** logspace

> **Comments:**
> **username_1**: Loop over each edge, cut it, and use USTCON to check if the two vertices are still connected.  
> **username_0**: 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.  
> **username_1**: 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.  
> **username_2**: @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.  
> **username_1**: Ah, right, I was implicitly thinking of something like USTCYCLE.  Apologies for the incorrect comment.  
> **username_3**: This is a standard textbook exercise, not a research-level problem so it is [off-topic, here](http://cstheory.stackexchange.com/help/on-topic).  
> **username_0**: Just to specify, this is not homework :) I'm studying for my exams, and I'm having some difficulty with the logarithmic space classes.  

---

## 1 answers

### Answer by username_4 on 2014-05-23. Score: 5 | Accepted answer

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.


---

