21
$\begingroup$

(crossposted from MathOverflow)

Hi,

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?

Improve this question
$\endgroup$
5
  • 3
    $\begingroup$ Crosspost from MO. $\endgroup$
    – Hsien-Chih Chang 張顯之
    Dec 14, 2010 at 7:23
  • $\begingroup$ Do your graphs have any special structure, other than being sparse? (Such as low degeneracy, for example.) $\endgroup$
    – Robin Kothari
    Dec 14, 2010 at 15:07
  • $\begingroup$ No, you can make the graph as diabolical as you want. Actually I don't even care if the graph is sparse: I'm considering a line graph $G$, and its underlying graph $H$ such that $G=L(H)$ (we can assume $H$ is simple). The reason I treat $|E(H)|$ and $|V(H)|$ the same is that I know $|E(H)|=|V(G)|$ and I want to analyze the complexity in terms of $|V(G)|$ and $|E(G)|$, but I can't say anything about how $|E(H)|$ compares to $|V(H)|$. $\endgroup$
    – Andrew D. King
    Dec 14, 2010 at 17:46
  • $\begingroup$ To be clear, you don't mind if the cycle contains repeated vertices, correct? $\endgroup$
    – user834
    Dec 14, 2010 at 21:28
  • $\begingroup$ I do not allow repeated vertices, but for a 5-cycle it doesn't matter because I assume the graph is simple and therefore has no 2-cycles. $\endgroup$
    – Andrew D. King
    Dec 15, 2010 at 15:04

2 Answers 2

Reset to default
21
$\begingroup$

To add to Mihai's answer:

Indeed, 5-cycle (and in general $k$-cycle) in sparse graphs can be solved much faster than $O(mn)$ time using the high degree / low degree trick. You need only look at another paper of Alon, Yuster and Zwick:

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.101.4120

For example, a 5-cycle can be found in $O(m^{1.67})$ time, without any dependence on matrix multiplication. See Theorem 3.4 of the above linked paper.

Also, while it is not too hard to reduce 5-cycle detection to Boolean matrix multiplication (with constant factor overhead), a reduction in the opposite direction does not appear in the color-coding paper. A tight reduction (which preserves the runtime complexity) from Boolean matrix multiplication to 5-cycle detection is not known.

Improve this answer
$\endgroup$
0
13
$\begingroup$

The dense case is essentially equivalent to boolean matrix multiplication by color coding. See http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.103.5167&rep=rep1&type=pdf.

For sparse graphs, there is an algorithm with time $O(mn)$ due to [B. Monien, How to find long paths efficiently, Ann. Discrete Math., 25 (1985), pp. 239-254]. I suspect something better might be possible by high-degree / low-degree tricks.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you! I will take a look at the Monien paper when I can get access to it. $\endgroup$
    – Andrew D. King
    Dec 16, 2010 at 4:45

Your Answer

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

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