Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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
1  
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

2 Answers 2

An answer containing a recursive formula for the number of cycles can be found here.

share|improve this answer

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

share|improve this answer
    
This includes cycles with repeated vertices, however. –  Rahul Mar 17 '11 at 17:58
1  
@Rahul Narain: And counts each of them m times. –  Max Mar 17 '11 at 18:09
    
I think this does not compute the number of simple cycles: As Rahul pointed out, this includes cycles with repeated vertices. –  Sadeq Dousti Mar 20 '11 at 16:37
    
I've got some answers to this question here. Have a look if you're interested... –  draks ... Aug 3 '12 at 6:23

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.