Showing Cycle is NL-complete?

Consider the following decision problem :


Cycle:
Given a directed graph G, does G contains a directed cycle?

It is very clear why Cycle belongs to NL.
My question is - how to show Cycle is also NL-hard?
it seems almost obvious to show logarithmic reduction from stCON. I thought about the following reduction:


Given a tuple (G, s, t), return G with a new edge (t,s).

Let us reduce direct connectivity to CYCLE.

We are given a directed graph $G$ and two vertices $s,t$. Suppose that $G$ contains $n$ vertices.

• We create $n$ copies of the vertices of $G$.

• For each edge $x \to y$ in $G$, we add an edge from the $i$th copy of $x$ to the $(i+1)$th copy of $y$.

• We also add an edge from each copy $i$ of $t$ to the first copy of $s$ (i.e. the edges $(t_i,s_1), i=1,...,n$).

The new graph contains a cycle iff $t$ is reachable from $s$ in $G$.

We can construct the new graph from the original graph in logspace. Hence this is a logspace reduction, which shows that CYCLE is NL-hard.

StackExchange Computer Science Q#109972, answer score: 6