2
$\begingroup$

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!

$\endgroup$
1
  • $\begingroup$ Can't you do some inclusion/exclusion if you know every cycle length? $\endgroup$ Aug 13, 2010 at 11:58

2 Answers 2

4
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$
    – damiano
    Aug 13, 2010 at 9:18
  • $\begingroup$ 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!)$. $\endgroup$
    – falagar
    Aug 13, 2010 at 9:36
  • $\begingroup$ 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)$. $\endgroup$
    – damiano
    Aug 13, 2010 at 9:40
  • $\begingroup$ 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!$. $\endgroup$
    – falagar
    Aug 13, 2010 at 9:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.