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