## Finding all cycles of a certain length in a graph

### Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

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 2010 at 11:58

## 3 Answers

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.

• Hongbo Liu; Jiaxin Wang; , "A new way to enumerate cycles in graph," Telecommunications, 2006. AICT-ICIW '06. International Conference on Internet and Web Applications and Services/Advanced International Conference on , vol., no., pp. 57- 57, 19-25 Feb. 2006 doi: 10.1109/AICT-ICIW.2006.22 URL: http://www.ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=1602189&isnumber=33674
-

### You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.

If you just want a recursion then let $C_k$ be the number of cycles of length $k$. You have the identity $$(A^k) _{ii}=\sum _{r\geq 2}C_r (A^{k-r}) _{ii}.$$

-

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 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!)$. – falagar 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)$. – damiano 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!$. – falagar Aug 13 2010 at 9:50
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 26, "mathjax_display_tex": 1, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.3, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9002171754837036, "perplexity_flag": "middle"}