Question

Hi,

I was reading this thread: http://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?

Answer 1

This paper talks about short cycle detection.

http://people.clarkson.edu/~ebollt/Papers/LComm.pdf

If it doesn't completely answer your question perhaps it can serve as a bound or as a starting point for further literature search.