2
$\begingroup$

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?

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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