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](http://www.tau.ac.il/~nogaa/PDFS/col5.pdf) 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?



Finding a cycle of fixed length
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)
> 
> 
> 


