= Solution
Here a directed cycle has at least one edge. If zero-length paths were treated as cycles, an edgeless one-vertex <graph> would already satisfy the predicate; that convention would give the trivial nonempty-graph predicate instead of the intended <directed cycle detection> problem.
For <NL> membership, guess a starting vertex $v$, follow a guessed directed walk for between one and $N=|V|$ edges, and accept if it returns to $v$. Store only the start, current vertex and step counter. A <graph> with a nonempty closed walk contains a simple directed cycle of at most $N$ edges, including a self-loop if present. Thus the algorithm uses <logarithmic space> and is complete for the predicate.
For hardness, reduce the <directed graph reachability problem> to cycle detection. Form $G^{(N+1)}$ and add the single backward arc
$$
(t,N+1)\longrightarrow(s,1).
$$
All layering arcs advance exactly one layer, including the waiting arcs $(v,i)\to(v,i+1)$, so the layered <graph> alone is a <Directed acyclic graph>. Any cycle in the augmented <graph> must contain the backward arc and therefore contains a path from $(s,1)$ to $(t,N+1)$.
If $t$ is reachable from $s$ in $G$, use a simple path of length at most $N-1$ and pad it with waits to exactly $N$ steps. It becomes the required layered path and closes to a cycle. Conversely, projecting such a layered path and deleting waits gives a walk from $s$ to $t$ in $G$. This includes the case $s=t$, where reachability has a zero-length witness but the augmented <graph> has a genuinely positive-length cycle.
There are $N(N+1)$ vertices and polynomially many arcs. A transducer enumerates pairs/layers and checks old adjacency by scanning its input, using only $O(\log N)$ bits. Hence this is a <logspace many-one reduction>, proving
$$
\boxed{\mathrm{CYCLE}\text{ is NL-complete}}.
$$
Back to article page
