# Finding all cycles of a certain length in a graph

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!

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

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.

-

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.

-
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