# Nondeterministic Logarithmic-space in directed graph

I continue to learn the complexity myself, currently I am interested in the complexity of space. I have read several books and tried some exercises as a practice. I would like to have your idea on the following problem.

Show that the problem of the existence of a cycle in a directed graph is a $$NL-complete$$ problem. To show that the problem is $$NL-hard$$, start from problem $$s; t-connectivity$$ and as an intermediate step, create a acyclic graph $$G^a$$ which is $$s’; t’- connected$$ if and only if the original graph $$G$$ is $$s; t- connected$$.

The author has set as hint: use the length of the paths of a vertex $$x$$ at a vertex $$y$$.

To show that the problem is in NL: guess a directed edge $$(u,v)$$ of the graph that is part of a cycle, and check (using the connectivity algorithm as a black-box, or by guessing each step of a walk) whether $$v$$ is connected to $$u$$ in $$G$$.

To show that the problem is NL-Hard create a new graph $$G'$$ as follows:

• For each vertex $$v$$ of $$G$$ add $$n$$ vertices $$v^{(0)},\dots,v^{(n-1)}$$ to $$G'$$.
• For each edge $$(u,v)$$ of $$G$$, and for each $$i=0,\dots,n-2$$, add the edge $$(u^{(i)}, v^{(i+1)})$$ to $$G'$$.

• For each $$i=0,\dots,n-2$$, add the edge $$(t^{(i)}, t^{(i+1)})$$ to $$G'$$.

It is easy to see that $$G'$$ is acyclic and that $$s^{(0)}$$ and $$t^{(n-1)}$$ are connected in $$G'$$ iff $$s$$ and $$t$$ are connected in $$G$$.

Now, consider the graph $$G''$$ obtained by adding the edge $$e=(t^{(n-1)}, s^{(0)})$$ to $$G'$$.

If $$s^{(0)}$$ and $$t^{(n-1)}$$ were connected by a path $$P$$ in $$G'$$, $$G''$$ contains the cycle $$C = P + e$$. The opposite direction is also true: if there is a cycle $$C$$ in $$G''$$ then $$C$$ must include $$e$$ and this means that of $$C-e$$ is a path between $$s^{(0)}$$ and $$t^{(n-1)}$$ in $$G'$$.

• thank you steven, now I understand much better – jenny forock Apr 7 at 18:18
• When you say black box, is it the oracle? – jenny forock Apr 7 at 18:31
• I just meant that you can invoke the algorithm for connectivity "as is", without caring of its inner workings. You can do this since that algorithm is also in NL. – Steven Apr 7 at 18:41