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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.