# 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/… – Hsien-Chih Chang 張顯之 Dec 5 '10 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? – Jeffε Dec 5 '10 at 17:02