(crossposted from MathOverflow)
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?