Finding a 5-cycle in a sparse graph efficiently. (crossposted from MathOverflow)

Hi,

I was reading this thread: https://mathoverflow.net/questions/16393/finding-a-cycle-of-fixed-length

I want to find a 5-cycle in a graph.  Actually, what I really want is a shortest odd cycle of length at least 5, but maybe that is a little beside the point.  For my purposes, I treat $m$ and $n$ the same in the complexity analysis.  

Can we do better than colour coding for finding a 5-cycle in this case?  Let me give a specific formulation of my question:


  What is the minimum $\alpha$ such that there is an $O(m^\alpha)$-time algorithm for detecting a cycle of length 5?  What is the algorithm?  And what is this $\alpha$ if you forbid impractical methods like Coppersmith-Winograd fast matrix multiplication?
To add to Mihai's answer:

Indeed, 5-cycle (and in general $k$-cycle) in sparse graphs can be solved much faster than $O(mn)$ time using the high degree / low degree trick. You need only look at another paper of Alon, Yuster and Zwick:

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.101.4120

For example, a 5-cycle can be found in $O(m^{1.67})$ time, without any dependence on matrix multiplication. See Theorem 3.4 of the above linked paper. 

Also, while it is not too hard to reduce 5-cycle detection to Boolean matrix multiplication (with constant factor overhead), a reduction in the opposite direction does not appear in the color-coding paper. A tight reduction (which preserves the runtime complexity) from Boolean matrix multiplication to 5-cycle detection is not known.