Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Hello,

I'm looking for a formula or algorithm to find the number of cycles of a certain length $k$ in a graph.

I know that $(A^k)_{ii}$ gives me the number of cycles from vertex $i$ to itself ($A$ is the adjacency matrix), but these are cycles that might contain the same vertex twice.

I have to tried to devise some sort of a recurrence formula but to no avail.

Thanks!

share|improve this question
    
Can't you do some inclusion/exclusion if you know every cycle length? –  Per Alexandersson Aug 13 '10 at 11:58

2 Answers 2

up vote 2 down vote accepted

Is your graph topologically planar or non-planar, weighted or unweighted, directed or undirected? Do you want an algorithm and/or a formula/bound?

For bounds on planar graphs, see Alt et al. On the number of simple cycles in planar graphs

For an algorithm, see the following paper. It incrementally builds k-cycles from (k-1)-cycles and (k-1)-paths without going through the rigourous task of computing the cycle space for the entire graph. It also handles duplicate avoidance.

share|improve this answer

If you consider only simple cycles (every vertex visited at most once) then this problem is NP-complete, so no polynomial (in $|G|$ and $k$) algorithm is known.

If non-polynomial algorithms are ok, you can use dynamic programming algorithm with complexity $O(\sum_{i=0}^{i\le k}\binom{n}{i}n^2)$. This algorithm calculates for every subset $S$ of at most $k$ vertices and every vertex $v \in S$ from this subset the number of paths that goes through all vertices from $S$ and has $v$ as the last vertex.

share|improve this answer
    
Is this algorithm better than enumerating the $k$-tuples of vertices and seeing if they are the vertices of a cycles in the given order? –  damiano Aug 13 '10 at 9:18
    
The number of $k$-tuples with distinct elements is $\frac{n!}{(n-k)!}$ which for big $k$ is much more than the number of subsets with at most $k$ elements. For example if $n=k$ then this algorithm works in time $O(n^2 2^n)$ and enumerating algorithm in time $O(n!)$. –  falagar Aug 13 '10 at 9:36
    
I see where our discrepancies lie: I had interpreted the question as fixing a certain value of k, whereas you are not doing this. For a fixed value of k, enumerating k-tuples seems to have complexity $O(\binom{n}{k})=O(n^k)$. –  damiano Aug 13 '10 at 9:40
    
Yes, if $k$ is fixed and we are interested only how time complexity depends on $n$ then both algorithms have the same complexity. They actually differ by a factor of $k!$. –  falagar Aug 13 '10 at 9:50

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.