<p>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.</p>

<p>What is the complexity class of $L'$? Can it be in $NL$?</p>

CC BY-SA 3.0
2014-10-10T17:55:02.277Z
From your crosspost on http://cs.stackexchange.com, your question appears to be for a class rather than a research level question.
Michael Blondin
CC BY-SA 3.0
2014-10-11T22:33:39.893Z
@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](http://cs.stackexchange.com/questions/30613/showing-that-a-language-is-in-nl) 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.
user12
CC BY-SA 3.0
2014-10-12T02:16:58.670Z
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.
Tsuyoshi Ito
CC BY-SA 3.0
2014-10-12T09:42:42.107Z
@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.
user12
CC BY-SA 3.0
2014-10-13T03:00:11.180Z
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.
Tsuyoshi Ito
CC BY-SA 3.0
2014-10-16T21:13:46.863Z
I would really appreciate if someone who voted to close could explain why?
user12
CC BY-SA 3.0
2014-10-19T11:09:06.057Z
I do not know other people’s reasons, but I already explained the reason why I voted to close, and I have already admitted that my reason was incorrect.
Tsuyoshi Ito
CC BY-SA 3.0
2014-10-19T11:10:25.760Z
I am not sure if you are still interested in reopening, but if you are, my suggestions are: (1) Please link to the crossposted question.  (2) Please give a proper citation for the source from which you took this question.  (3) Please explain why you think this is not an exercise-level question but a research-level question.  I do not think this is at the level of typical textbook exercises, but because this is your question, please justify posting here by yourself.  (4) Please give a descriptive title; the current title is too general to be useful.
Tsuyoshi Ito
CC BY-SA 3.0
2014-10-19T11:12:04.607Z
I cannot promise that following some or all of my suggestions will reopen the question, but I believe that doing so will make reopening more probable.
Tsuyoshi Ito
<cc.complexity-theory><complexity-classes>
Determine the complexity class of a language
user12
# Determine the complexity class of a language

(Asked by: username_0 on 2014-10-10)

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

**Tags:** cc.complexity-theory, complexity-classes

> **Comments:**
> **username_1**: From your crosspost on http://cs.stackexchange.com, your question appears to be for a class rather than a research level question.  
> **username_0**: @username_1 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](http://cs.stackexchange.com/questions/30613/showing-that-a-language-is-in-nl) 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.  
> **username_2**: 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.  
> **username_0**: @username_2 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.  
> **username_2**: 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.  
> **username_0**: I would really appreciate if someone who voted to close could explain why?  
> **username_2**: I do not know other people’s reasons, but I already explained the reason why I voted to close, and I have already admitted that my reason was incorrect.  
> **username_2**: I am not sure if you are still interested in reopening, but if you are, my suggestions are: (1) Please link to the crossposted question.  (2) Please give a proper citation for the source from which you took this question.  (3) Please explain why you think this is not an exercise-level question but a research-level question.  I do not think this is at the level of typical textbook exercises, but because this is your question, please justify posting here by yourself.  (4) Please give a descriptive title; the current title is too general to be useful.  
> **username_2**: I cannot promise that following some or all of my suggestions will reopen the question, but I believe that doing so will make reopening more probable.  

---

## 0 answers

