Question

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?

Answer 1

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)

Answer 2

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.

Answer 3

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