<p>Perhaps this paper which deals with cycle lengths in planar graphs might be of value:</p>

<p>Li, Ming-Chu; Corneil, Derek G.; Mendelsohn, Eric (2000), "Pancyclicity and NP-completeness in planar graphs", Discrete Applied Mathematics 98 (3): 219–225.</p>

CC BY-SA 2.5
2010-12-05T17:35:04.983Z
2010-12-05T17:35:04.983Z
Joseph Malkevitch
<p>G is a planar graph with n nodes.<br>
What are the complexity of following problems?</p>

<p>1-A: Does G contain an m-cycle? (m-cycle is a simple cycle with m nodes, m&lt; n)<br>
2-B: complexity of counting all m-cycles in G, (Complexity of #A).</p>

<p>3- what is the complexity of A and B if G is an arbitrary given graph? </p>

<p>Pointing to books and papers is also useful...</p>

CC BY-SA 2.5
2010-12-05T10:37:55.310Z
For 1, since by adding one node to G and letting $m=n-1$ we have reduced to the Hamiltonian cycle problem, it is NP-hard in general. For $m$ is a fixed constant, see my questions on MathOverflow: http://mathoverflow.net/questions/16393/finding-a-cycle-of-fixed-length, http://mathoverflow.net/questions/35560/finding-a-subgraph-with-slightly-large-size-in-planar-graphs
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2010-12-05T14:57:18.273Z
Marjoonjan, it would be nice if you also explain why *you* are personally interested in these question, e.g. are you working on a problem which is related to your question? Please read [How to ask a good question? ](http://meta.cstheory.stackexchange.com/questions/300/how-to-ask-a-good-question), specially [this one](http://meta.cstheory.stackexchange.com/questions/300/how-to-ask-a-good-question/318#318).
Kaveh
CC BY-SA 2.5
2010-12-05T15:46:12.217Z
Dear Kave, I read those links and I think I obey the suggested answers for how to ask a question! I am seriously working on a problem which is related to both computational geometry and theory of complexity, and all my questions are related to what I'm thinking about them, during whole day, to solve a difficult problem! could I answer your question?
marjoonjan
CC BY-SA 2.5
2010-12-05T17:02:39.460Z
What problem are you working on?  Why is this question relevant?  What do you already know?  (For example: *You* should have said that problem 1 is NP-hard when $m=n-1$ but clearly in P when $m=O(1)$.  Otherwise, we're led to believe that you haven't thought about the problem at all.)  What have you tried?
Jeffε
CC BY-SA 2.5
2010-12-05T18:13:22.863Z
:))come on, Jeffe please!what do u mean? I didn't ask about m-cycles when m=n-1, Hsien replied that in this case some results are known! Is it a trial?How can I explain u what my problem exactly is? I myself am eager to share it with u all! Its title is "Counting inducing n-gons in arrangement of lines." as I explained before this is the problem which needs knowledges both in Computational Geometry and Complexity Theory. I agree with u that my knowledge about Complexity is'nt enough and this is exactly why I am here!could I convince u or u insist on believing I know nothing about the problem?!
marjoonjan
CC BY-SA 2.5
2010-12-05T19:15:13.457Z
@JeffE: Dear JeffE if the first question is so simple please focuse on the remaining questions, and share your idea about them!
marjoonjan
CC BY-SA 2.5
2010-12-05T19:30:20.760Z
@marjoonjan, the commenters are merely trying to help you craft a better question. Your original question should have described the set of results that are already known (m = n-1, constant, or even), and then focused on the range of values of m that you care about for your application. Given the comments, it is really your job to now explain why the question remains interesting, because Hsien-Chih's answer already captures many interesting cases. Explaining your original motivation might also help because it's possible that this isn't even the right question.
Suresh Venkat
CC BY-SA 2.5
2010-12-06T00:55:34.457Z
@marjoonjan: While your questions can be answered as a [reference-request] problem in your current presentation, however, we want to help more!! Maybe you think that the community is strict and want you to provide lots of background information which you may not think it is needed. But that will take you a lot of time surveying all the literatures we provided (and maybe there is too much so we do not know how to start). Maybe after explaining some of your motivations, we can concentrate on what you really need, and answer you questions more precisely and accurately. Help us to help you!! :)
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2010-12-06T01:03:15.183Z
@marjoonjan: Another random thought: maybe you can try to provide the actual problem you are now solving? You have mentioned that "I am seriously working on a problem which is related to ...", so what is the problem? Maybe someone in the community have surveyed it! And then he/she can give you a decent answer, much better than some general literature I can provide (since I know almost nothing about counting).
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2010-12-06T02:01:59.587Z
@marjonnan: If you want to get help from this community, you need to make a good faith effort to convince us that you're not just asking us to do your work for you.  Please meet us halfway.
Jeffε
CC BY-SA 2.5
2010-12-06T07:56:00.960Z
Ok,Let's be friend =; don't judge me like this :(... I want to trust u and share my original problem! the following link is my submitted paper in SOCG2011, those who know computational geometry are familiar whith this lecture note well. please read the abstract,Introduction, definitions and conclusion! then I can tell u what is in my mind to solve what is mentiond in conclusion for future works! I dont know what else I can do to make a good faith effort to convince u :) http://rapidshare.com/files/435200959/socg2011_submission.pdf
marjoonjan
CC BY-SA 2.5
2010-12-06T11:48:40.027Z
@marjoonjan: the link may be broken!
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2010-12-06T15:39:37.987Z
I dont know why the problem occures, I upload the file again and test it! It works properly! I omited the parts which are not related to what u need to know! just see what is arrangement of lines- Inducing polygon! then if anyone were eager to continue I can share my ideas with him! Or I dont know... any other ideas are also welcome!http://rapidshare.com/files/435271389/Final2.pdf
marjoonjan
<cc.complexity-theory><graph-theory><complexity-classes>
Complexity of counting m-cycles in a graph with n nodes
marjoonjan
# Complexity of counting m-cycles in a graph with n nodes

(Asked by: username_0 on 2010-12-05)

G is a planar graph with n nodes.  
What are the complexity of following problems?

1-A: Does G contain an m-cycle? (m-cycle is a simple cycle with m nodes, m< n)  
2-B: complexity of counting all m-cycles in G, (Complexity of #A).

3- what is the complexity of A and B if G is an arbitrary given graph?

Pointing to books and papers is also useful...

**Tags:** cc.complexity-theory, graph-theory, complexity-classes
> **Comments:**
> **username_1**: For 1, since by adding one node to G and letting $m=n-1$ we have reduced to the Hamiltonian cycle problem, it is NP-hard in general. For $m$ is a fixed constant, see my questions on MathOverflow: http://mathoverflow.net/questions/16393/finding-a-cycle-of-fixed-length, http://mathoverflow.net/questions/35560/finding-a-subgraph-with-slightly-large-size-in-planar-graphs  
> **username_2**: Marjoonjan, it would be nice if you also explain why *you* are personally interested in these question, e.g. are you working on a problem which is related to your question? Please read [How to ask a good question? ](http://meta.cstheory.stackexchange.com/questions/300/how-to-ask-a-good-question), specially [this one](http://meta.cstheory.stackexchange.com/questions/300/how-to-ask-a-good-question/318#318).  
> **username_0**: Dear Kave, I read those links and I think I obey the suggested answers for how to ask a question! I am seriously working on a problem which is related to both computational geometry and theory of complexity, and all my questions are related to what I'm thinking about them, during whole day, to solve a difficult problem! could I answer your question?  
> **username_3**: What problem are you working on?  Why is this question relevant?  What do you already know?  (For example: *You* should have said that problem 1 is NP-hard when $m=n-1$ but clearly in P when $m=O(1)$.  Otherwise, we're led to believe that you haven't thought about the problem at all.)  What have you tried?  
> **username_0**: :))come on, Jeffe please!what do u mean? I didn't ask about m-cycles when m=n-1, Hsien replied that in this case some results are known! Is it a trial?How can I explain u what my problem exactly is? I myself am eager to share it with u all! Its title is "Counting inducing n-gons in arrangement of lines." as I explained before this is the problem which needs knowledges both in Computational Geometry and Complexity Theory. I agree with u that my knowledge about Complexity is'nt enough and this is exactly why I am here!could I convince u or u insist on believing I know nothing about the problem?!  
> **username_0**: @JeffE: Dear JeffE if the first question is so simple please focuse on the remaining questions, and share your idea about them!  
> **username_4**: @marjoonjan, the commenters are merely trying to help you craft a better question. Your original question should have described the set of results that are already known (m = n-1, constant, or even), and then focused on the range of values of m that you care about for your application. Given the comments, it is really your job to now explain why the question remains interesting, because Hsien-Chih's answer already captures many interesting cases. Explaining your original motivation might also help because it's possible that this isn't even the right question.  
> **username_1**: @marjoonjan: While your questions can be answered as a [reference-request] problem in your current presentation, however, we want to help more!! Maybe you think that the community is strict and want you to provide lots of background information which you may not think it is needed. But that will take you a lot of time surveying all the literatures we provided (and maybe there is too much so we do not know how to start). Maybe after explaining some of your motivations, we can concentrate on what you really need, and answer you questions more precisely and accurately. Help us to help you!! :)  
> **username_1**: @marjoonjan: Another random thought: maybe you can try to provide the actual problem you are now solving? You have mentioned that "I am seriously working on a problem which is related to ...", so what is the problem? Maybe someone in the community have surveyed it! And then he/she can give you a decent answer, much better than some general literature I can provide (since I know almost nothing about counting).  
> **username_3**: @marjonnan: If you want to get help from this community, you need to make a good faith effort to convince us that you're not just asking us to do your work for you.  Please meet us halfway.  
> **username_0**: Ok,Let's be friend =; don't judge me like this :(... I want to trust u and share my original problem! the following link is my submitted paper in SOCG2011, those who know computational geometry are familiar whith this lecture note well. please read the abstract,Introduction, definitions and conclusion! then I can tell u what is in my mind to solve what is mentiond in conclusion for future works! I dont know what else I can do to make a good faith effort to convince u :) http://rapidshare.com/files/435200959/socg2011_submission.pdf  
> **username_1**: @marjoonjan: the link may be broken!  
> **username_0**: I dont know why the problem occures, I upload the file again and test it! It works properly! I omited the parts which are not related to what u need to know! just see what is arrangement of lines- Inducing polygon! then if anyone were eager to continue I can share my ideas with him! Or I dont know... any other ideas are also welcome!http://rapidshare.com/files/435271389/Final2.pdf  

---

## 1 answers

### Answer by username_5 on 2010-12-05. Score: 2

Perhaps this paper which deals with cycle lengths in planar graphs might be of value:

Li, Ming-Chu; Corneil, Derek G.; Mendelsohn, Eric (2000), "Pancyclicity and NP-completeness in planar graphs", Discrete Applied Mathematics 98 (3): 219–225.


---

