Welcome to MathOverflow

Question

2

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!

flag	asked Aug 13 2010 at 8:54 R S 381●7

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

SandeepJ · Accepted Answer · 2010-08-13 19:28:26Z UTC

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

Gjergji Zaimi · Answer 2 · 2010-08-13 09:20:40Z UTC

2

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}.$$

answered Aug 13 2010 at 9:20

Gjergji Zaimi
37.3k●2●72●149

falagar · Answer 3 · 2010-08-13 09:34:38Z UTC

0

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.

edited Aug 13 2010 at 9:34

answered Aug 13 2010 at 9:14

falagar
1,703●4●23

	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

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)

3 Answers

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.