Search code examples
algorithmgraphcycle

Solving cycle in undirected graph in log space?

A slightly more theoretical question, but here it is nonetheless.

Setting

Let: UCYLE = { : G is an undirected graph that contains a simple cycle}.

My Solution

we show UCYLE is in L by constructing algorithm M that decides UCYLE using $L$ space.

M = "On input where G = (V,E)

  1. For each v_i in V, for each v_j in Neighbor(v_i), store the current v_i and v_j

  2. Traverse the edge (v_i,v_j) and then follow all possible paths through G using DFS.

  3. If we encounter v_k in Neighbor(v_i) / {v_j} so that there is an edge (v_i,v_k) in E, then ACCEPT. Else REJECT."

First we claim M decides UCYLE. First, if there exists a cycle in $G$, then it must start and end on some vertex $v_i$, step one of $M$ tries all such $v_i$'s and therefore must find the desired vertex. Next, suppose the cycle starts at $v_i$, then there must exists a starting edge $(v_i,v_j)$ so that if we follow the cycle, we come back to $v_i$ through a different edge $(v_k,v_i)$, so we accept in step three. Since the graph is undirected, we can always come back to $v_i$ through $(v_i,v_j)$, but $M$ does not accept this case. By construction, neither does $M$ accept if we come upon some $v_k in Neighbor(v_i)/{v_j}$ but there is no edge from $v_k$ to $v_i$.

Now we show M is in L. First if the vertices are labled $1,\ldots,n$ where $|\mathbb V| = n$, then it requires $log(n)$ bits to specify each $v_i$. Next note in $\mathcal M$ we only need to keep track of the current $v_i$ and $v_j$, so M is $2 log(n) = O(log n), which is in L

My Problem

My problem is how do you perform DFS on the graph in $log(n)$ space. For example, in the worst case where each vertex has degree $n$, you'd have to keep a counter of which vertex you took on a particular path, which would require $n log(n)$ space.

Solution

  • The state you maintain as you search is four vertices: (v_i, v_j, prev, current).

    The next state is: (v_i, v_j, current, v) where v is the next neighbour of current after prev (wrapping back to the first if prev is the numerically last neighbour of current).

    You stop when current is a neighbour of v_i and reject if it's not v_j.

    In pseudo-code, something like this:

    for v_i in vertices
    for v_j in neighbours(v_i)
        current, prev = v_j, v_i
        repeat
            idx = neighbours(current).index(prev)
            idx = (idx + 1) % len(neighbours(current))
            current, prev = neighbours(current)[idx], current
        until current adjacent to v_i
        if current != v_j 
            return FOUND_A_CYCLE
return NO_CYCLES_EXIST

    Intuitively, this is saying for each point in a maze, and for each corridor from that point, follow the left-hand wall, and if when you can see the start point again if it's not through the original corridor then you've found a cycle.

    While it's easy to see that this algorithm uses O(log n) space, there's some proof necessary to show that this algorithm terminates.