# Showing that the language of graphs and nodes on an odd cycle is in NL

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?

• And what exactly is your question? What have you tried and where did you get stuck, in detail? – Raphael Oct 5 '14 at 14:17
• 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. – user12 Oct 5 '14 at 14:29
• 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? – zarathustra Oct 6 '14 at 15:04
• I believe that it should be counted as a cycle. – user12 Oct 6 '14 at 15:13
• 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. – zarathustra Oct 6 '14 at 15:23

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.