# Complexity of counting m-cycles in a graph with n nodes

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

• 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: mathoverflow.net/questions/16393/…, mathoverflow.net/questions/35560/… Dec 5, 2010 at 10:37
• 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? Dec 5, 2010 at 17:02
• @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!! :) Dec 6, 2010 at 0:55
• @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. Dec 6, 2010 at 2:01

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.