# 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? Aug 13, 2010 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? Aug 13, 2010 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!)$. Aug 13, 2010 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)$. Aug 13, 2010 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!$. Aug 13, 2010 at 9:50