Past exam of the mathematics course of the University of Cambridge / 2013 / iii / Paper 59 / 2 / b / 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 arcAll 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