Is there any result about the time complexity of finding a cycle of fixed length $k$ in a general graph? All I know is that Alon, Yuster and Zwick use a technique called "color-coding", which has a running time of $O(M(n))$, where $n$ is the number of vertices of the input graph and $M(n)$ is the time required to multiply two $n \times n$ matrices.

Is there any better result?

  • 1
    $\begingroup$ I suppose your n is the number of nodes in the graph. $\endgroup$ – HenrikRüping Feb 25 '10 at 15:21
  • $\begingroup$ Yes, it is. Thanks for the supplement. $\endgroup$ – Hsien-Chih Chang 張顯之 Feb 26 '10 at 7:27

Finding a cycle of any even length can be found in $O(n^2)$ time, which is less than any known bound on $O(M(n))$. For example, a cycle of length four can be found in $O(n^2)$ time via the following simple procedure:

Assume the vertex set is $\{1,...,n\}$. Prepare an $n$ x $n$ matrix $A$ which is initially all zeroes. For all vertices $i$ and all pairs of vertices $j, k$ which are neighbors to $i$, check $A[j,k]$ for a $1$. If it has a $1$, output four-cycle, otherwise set $A[j,k]$ to be $1$. When this loop finishes, output no four-cycle.

The above algorithm runs in at most $O(n^2)$ time, since for every triple $i,j,k$ we either flip a $0$ to $1$ in $A$, or we stop. (We assume the graph is in adjacency list representation, so it is easy to select pairs of neighbors of a vertex.)

The general case is treated by Raphy Yuster and Uri Zwick in the paper:

Raphael Yuster, Uri Zwick: Finding Even Cycles Even Faster. SIAM J. Discrete Math. 10(2): 209-222 (1997)

As for finding cycles of odd length, it's just as David Eppstein says: nothing better is known than $O(M(n))$, including the case where $k=3$.

However, if you wished to detect paths of length $k$ instead of cycles, you can indeed get $O(m+n)$ time, where $m$ is the number of edges. I am not sure if the original color-coding paper can provide this time bound, but I do know that the following paper by some random self-citing nerd gets it:

Ryan Williams: Finding paths of length k in O*(2^k) time. Inf. Process. Lett. 109(6): 315-318 (2009)

  • $\begingroup$ Thank you for mentioning the result about detecting paths. It's new to me and it is very useful. Thanks!! $\endgroup$ – Hsien-Chih Chang 張顯之 Feb 26 '10 at 7:20
  • 2
    $\begingroup$ A linear time algorithm (i.e., O(m+n)) for detecting paths of length k was mentioned in one of Alon et al.'s papers. It just involves choosing a random ordering of the vertices, and making the graph a DAG using this ordering. Since longest path on DAGs can be solved in linear time, a directed path of length k can be found in linear time, if the chosen random ordering works. Repeat the previous step exponentially many times (in k), to get desired randomized algorithm. $\endgroup$ – Rune Mar 1 '10 at 23:59
  • 1
    $\begingroup$ Good stuff. How can I detect every cycle of length 4 though? The algorithms you reference seem to only tell you if such a cycle exists or not. $\endgroup$ – Nicu Stiurca Nov 5 '13 at 1:10
  • 1
    $\begingroup$ Not sure what you're asking. There can be $\Omega(n^4)$ cycles of length 4 in a graph, so $O(n^4)$ time is the best you can hope for asymptotically if you want to list all 4-cycles. If you're asking how to get the above algorithm to produce a 4-cycle in $O(n^2)$ time when one exists, that's also pretty obvious... $\endgroup$ – Ryan Williams Nov 5 '13 at 9:33
  • 1
    $\begingroup$ At first I wondered why you insulted Ryan Williams... $\endgroup$ – quietContest Jul 24 '16 at 1:53

If there's a deterministic or randomized algorithm with better dependence on $n$ than $M(n)$ even for the first nontrivial case, $k=3$ (that is, testing whether the given graph contains a triangle) then I don't know about it. Nothing better is listed on the Wikipedia article on triangle-free graphs, for instance. There do exist quantum algorithms for finding 3-cycles that are faster, however: see arXiv:quant-ph/0310134.

It's also possible to find bounds that are better than $M(n)$ for graphs that are not dense (number of edges sufficiently smaller than quadratic). For instance even fairly naive algorithms can find triangles in time $O(m^{3/2})$ where $m$ is the number of edges in the graph.

  • $\begingroup$ Thanks for the useful information. I also noticed that for planar graph you gave a linear time algorithm for detecting any bounded size graph. Thank you very much!! $\endgroup$ – Hsien-Chih Chang 張顯之 Feb 26 '10 at 7:18

If we restrict to the class of planar graphs, then there is a linear time algorithm due to Eppstein. It is also linear for graphs of bounded tree-width since the problem of finding a cycle of fixed length can easily be encoded as a monadic second-order logic formula, and we can then appeal to Courcelle's theorem.

Edit. The related problem of finding a cycle of length $a$ (mod $k$) has not been proven to be polynomial (except in the case $a=0$).

  • $\begingroup$ A polynomial bound for general graphs (for any fixed k) is given by the Alon et al color-coding paper that the original question cites. $\endgroup$ – David Eppstein Feb 25 '10 at 21:22
  • $\begingroup$ Finding a cycle of length being a multiple of k is a pretty interesting question. Thanks for the information! $\endgroup$ – Hsien-Chih Chang 張顯之 Feb 26 '10 at 7:25
  • $\begingroup$ If we consider graphs with edges labelled from a finite abelian group, then we can define the group-value of a cycle as the sum of its edge labels. For a fixed element g of the group, we can then ask if there is cycle with group-value g. Cycles of length 0 (mod k) are a special instance of this problem, where the group is $Z_k$, g=0, and all edge labels are 1. $\endgroup$ – Tony Huynh Feb 26 '10 at 15:51

Basically everyone above hit the nail on its head. I want to add an algorithm of counting every cycles of length 4 in an undirected graph, which runs in $O(n^3)$ instead of $O(n^4)$

Every cycle of length four includes four nodes $a$, $b$, $c$ and $d$. Thus for every pair of nodes, $u$ and $v$, you count the number of nodes that are neighbors to both $u$ and $v$. Then the problem of counting every cycle of length four transforms to the problem of selecting 2 such nodes that are adjacent to both $u$ and $v$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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