Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
1  
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
add comment

3 Answers 3

up vote 11 down vote accepted

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)

share|improve this answer
    
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
2  
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
add comment

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

share|improve this answer
    
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
add comment

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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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