2
$\begingroup$

Setting

Let: $$UCYLE = \mathcal \{ <G> ~:~ G \text{ is an undirected graph that contains a simple cycle}\}.$$

My Solution

we show $UCYLE \in L$ by constructing $\mathcal M$ that decides $UCYLE$ using $L$ space.

$\mathcal M = $"On input $<G>$ where $G = (\mathbb V, \mathbb E)$:

  1. For each $v_i \in \mathbb 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 \mathbb E$, then ACCEPT. Else REJECT."

First we claim $\mathcal 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 $\mathcal 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 $\mathcal M$ does not accept this case. By construction, neither does $\mathcal 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$.\newline

Now we show $\mathcal M \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 $\mathcal M$ is $2 log(n) = O(log ~n) \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.

$\endgroup$
4
$\begingroup$

The trick is to use Reingold's result that undirected reachability is in logspace. For each vertex $v$, we check whether the connected component containing $v$ contains a cycle by counting the number of vertices and edges. We do that by going over all vertices $u$, check whether $u$ is reachable from $v$, and if so, increase the vertex counter by 1 and the edge counter by half the degree of $u$. After going over all vertices, we have counted the number of vertices $V$ and edges $E$ in the connected component containing $v$. This component contains a cycle if and only if $E \geq V$.

$\endgroup$

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.