# Cycles of Specified Length in a Graph

Let $G=(V,E)$ be a graph, and $A$ be its adjacency matrix. Define $n = |V|$.

Given $A$ and a natural number $m \le n$, I'm interested in the following problem:

How many simple cycles of length $m$ exist in $G$?

By simple cycle, I mean no repeated vertices along the cycle is allowed (other than the starting and ending vertices, which coincide).

The problem is NP-hard. However, I'm not asking its complexity; I'm merely interested in whether there is a closed-form expression for computing it. (Thus, computing the expression can be NP-hard.)

-
This is indeed NP-hard: when $m = n$, whether the number of simple cycles of length $m$ is nonzero is the Hamiltonian path problem. –  Rahul Mar 17 '11 at 18:09
@Rahul: I know. I used the word "might" since for $m<n$, it might be easier. –  Sadeq Dousti Mar 17 '11 at 18:19
Hi, I asked the same question without noticing yours. Sorry for that, but I got some pretty cool answers (one containing a recursive formula to calculate the number of ways without backtracking). If you are still interested, have a look. And +1 interesting question ;-) –  draks ... Aug 2 '12 at 18:04
Interesting, in a comment it is stated, that the number of cycles can be computed in polynomial time. So why do you say, that it is NP-hard? For a better flow of reading it would be cool, if could reply directly to Chris there... –  draks ... Aug 3 '12 at 18:06
@draks: Maybe our questions are different? –  Sadeq Dousti Aug 4 '12 at 7:19

I think the trace of $A^m$ gives the number of cycles of length $m$ of a graph $G$.