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 (s,t).