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

$\endgroup$
1
$\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'$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ thank you steven, now I understand much better $\endgroup$ – jenny forock Apr 7 at 18:18
  • $\begingroup$ When you say black box, is it the oracle? $\endgroup$ – jenny forock Apr 7 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$ – Steven Apr 7 at 18:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.