Let L be the language containing all the pairs (G,v) where G is a directed graph and v is a vertex in G such that G contains a cycle that contains v and the number of different vertices that appear in that cycle is odd. Find the smallest class (NP, P or NL) that contains L.

Clearly L is in NP, I didn't manage to show that it is in P so I tried to show that it's NP-Complete, however the answer in the textbook is NL?

  • 2
    $\begingroup$ And what exactly is your question? What have you tried and where did you get stuck, in detail? $\endgroup$ – Raphael Oct 5 '14 at 14:17
  • $\begingroup$ I have tried to show that the language is in NL, but I didn't find a correct solution. I don't think that there is a need to describe solutions that I know that are incorrect. $\endgroup$ – user12 Oct 5 '14 at 14:29
  • $\begingroup$ Just to be sure: if there is a sequence $u_1\dots u_{k-1}u_ku_{k-1}\dots u_1$ where each vertex has an arc to the following one, does that count as a cycle? $\endgroup$ – zarathustra Oct 6 '14 at 15:04
  • $\begingroup$ I believe that it should be counted as a cycle. $\endgroup$ – user12 Oct 6 '14 at 15:13
  • $\begingroup$ So, let us call $(s,t,n)$-connectivity the problem of deciding whether there exists a path of length exactly $n$ from $s$ to $t$ in the input. This problem is in $\mathsf{NL}$ (the proof is very much like the proof that $(s,t)$-connectivity is in $\mathsf{NL}$). Then wouldn't the following solve the problem? Guess a node $u$ in the graph, then for each odd number $1\leq k\leq n$, and each decomposition $k=k_1+k_2$ into two integers, solve the problems of $(v,u,k_1)$-connectivity and $(u,v,k_2)$-connectivity? I can elaborate in an answer if you don't detect any bug in this. $\endgroup$ – zarathustra Oct 6 '14 at 15:23

The question is ambiguous. Specifically, it is not clear what "different vertices that appear in that cycle" means. It can mean two things (1) the size of the set of nodes that appear in the path, or (2) the total number of nodes in that path, i.e., the length of that cycle (minus 1).

If the interpretation is (2), then the language is clearly NL: you perform a random walk (of length $\le n$), counting the number of nodes you see. If you get back to $v$ and the number of nodes is odd, you accept, otherwise you reject.

If the interpretation is (1), I don't see an immediate way to show it is in NL.


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.