1
$\begingroup$

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$.

Improve this question
$\endgroup$
2

1 Answer 1

Reset to default
4
$\begingroup$

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'$.

Improve this answer
$\endgroup$
2
  • $\begingroup$ When you say black box, is it the oracle? $\endgroup$ Commented Apr 7, 2020 at 18:31
  • $\begingroup$ 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. $\endgroup$ Commented Apr 7, 2020 at 18:41

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.