= Directed cycle detection
Decide whether a <directed graph> has a nonempty directed cycle; self-loops count. This problem is <NL-complete>. Membership guesses a returning walk of at most the vertex count. For hardness, layer a reachability instance into $N+1$ layers with wait arcs, then add only the backward edge from the target in the last layer to the source in the first. The otherwise acyclic layering has a cycle exactly when the original target is reachable. Zero-length paths must not be treated as cycles.
Back to article page
