Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Hi,

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

share|improve this question

1 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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.