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 (i.e. closed walk) that contains $v$ and the number of different vertices that appear in that cycle is odd.

What is the complexity class of $L'$? Can it be in $NL$?


closed as off-topic by Emil Jeřábek supports Monica, Kristoffer Arnsfelt Hansen, R B, Tsuyoshi Ito, domotorp Oct 11 '14 at 12:59

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Your question does not appear to be a research-level question in theoretical computer science. For more information about the scope, please see help center. Your question might be suitable for Computer Science which has a broader scope." – Emil Jeřábek supports Monica, Kristoffer Arnsfelt Hansen, R B, Tsuyoshi Ito, domotorp
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ From your crosspost on cs.stackexchange.com, your question appears to be for a class rather than a research level question. $\endgroup$ – Michael Blondin Oct 10 '14 at 17:55
  • $\begingroup$ @Michael Blondin I found this language in a small textbook that contains a collection of problems and their complexity classes without giving any proofs. When I first saw this language I didn't understand why it is in NL. I searched for a similar result but didn't manage to find one so I tried asking it on cs but didn't get any answer for about a week. I really apologize for posting this question here, I didn't know that it is not suitable for this site. I just wanted to know if the result is true. I'm sorry. $\endgroup$ – user12 Oct 11 '14 at 22:33
  • 1
    $\begingroup$ I am afraid that I may have voted to close while misunderstanding the question. I thought that the question was about an odd cycle (in which case it is easy to see the problem is in NL), but it is apparently not. Just to clarify, if the given directed graph consists of two cycles v→a→b→c→v and v→d→e→f→v, is the answer YES because it contains a closed walk v→a→b→c→v→d→e→f→v which indeed contain 7 different vertices? If so, I do not know how to prove that the problem is in NL. $\endgroup$ – Tsuyoshi Ito Oct 12 '14 at 2:16
  • $\begingroup$ @Tsuyoshi Ito You are right. The answer in this case is YES because it contains the closed walk v→a→b→c→v→d→e→f→v. $\endgroup$ – user12 Oct 12 '14 at 9:42
  • $\begingroup$ Because I could no longer say this question is not at research level, I voted to reopen. If four other people with enough rep points agree, the question will be reopened. $\endgroup$ – Tsuyoshi Ito Oct 13 '14 at 3:00