4
$\begingroup$

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

  • 0
    This is indeed NP-hard: when $m = n$, whether the number of simple cycles of length $m$ is nonzero is the Hamiltonian path problem.2011-03-17
  • 0
    @Rahul: I know. I used the word "might" since for $m2011-03-17
  • 2
    Hi, I asked the [same question](http://math.stackexchange.com/q/177722/19341) 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** ;-)2012-08-02
  • 0
    Interesting, in a [comment](http://math.stackexchange.com/questions/177722/19341#comment410736_177865) 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...2012-08-03
  • 0
    @draks: Maybe our questions are different?2012-08-04
  • 0
    @draks: Like you, I got the impression that our questions are the same! If you agree that they're not, please tell me to "un-accept" it. You can also delete your answer. Thanks.2012-08-04
  • 0
    I'm pretty sure that they are the same. I just wonder about the different complexities given by you and Chri and so I want to hear your opinion...2012-08-05
  • 0
    For the problem I stated here, I'm also pretty sure that it is NP-complete. Take a look at page 4 on [this presentation](http://idv.sinica.edu.tw/josephcclin/paper/counting-cycles.pdf), or its [full version](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.101.4120).2012-08-07
  • 0
    I think the difference is that your cycles are **simple**, no repeated vertices, while mine are **reduced** ones, no backtracking. What do you think?2012-11-06
  • 0
    @draks: That's one possible difference. Small changes in problem definition may have drastic effects on its computational complexity.2012-11-07

2 Answers 2

1

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

0

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

  • 0
    This includes cycles with repeated vertices, however.2011-03-17
  • 2
    @Rahul Narain: And counts each of them m times.2011-03-17
  • 0
    I think this does not compute the number of **simple** cycles: As Rahul pointed out, this includes cycles with repeated vertices.2011-03-20
  • 0
    I've got some answers to this question [here](http://math.stackexchange.com/q/177722/19341). Have a look if you're interested...2012-08-03