# Finding a cycle of fixed length

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 Noga Alon et al. use the techinique called "color-coding", which has a running time O(M(n)), where M(n) is the time of multiplying two n times n matrices.

Is there any better result?

-
I suppose your n is the number of nodes in the graph. –  HenrikRüping Feb 25 '10 at 15:21
Yes, it is. Thanks for the supplement. –  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)

-
Thank you for mentioning the result about detecting paths. It's new to me and it is very useful. Thanks!! –  Hsien-Chih Chang 張顯之 Feb 26 '10 at 7:20
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. –  Rune Mar 1 '10 at 23:59
Rune is absolutely right; the random ordering algorithm runs in O(k! (m + n)) time. –  Ryan Williams Mar 2 '10 at 6:11
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. –  SchighSchagh Nov 5 '13 at 1:10
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... –  Ryan Williams Nov 5 '13 at 9:33

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. I suspect that the answer for general graphs is actually polynomial.

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

-
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. –  David Eppstein Feb 25 '10 at 21:22
Finding a cycle of length being a multiple of k is a pretty interesting question. Thanks for the information! –  Hsien-Chih Chang 張顯之 Feb 26 '10 at 7:25
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. –  Tony Huynh Feb 26 '10 at 15:51

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.

-
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!! –  Hsien-Chih Chang 張顯之 Feb 26 '10 at 7:18