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?

$\endgroup$
  • 3
    $\begingroup$ Crosspost from MO. $\endgroup$ – Hsien-Chih Chang 張顯之 Dec 14 '10 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 '10 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 '10 at 17:46
  • $\begingroup$ To be clear, you don't mind if the cycle contains repeated vertices, correct? $\endgroup$ – user834 Dec 14 '10 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 '10 at 15:04
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.

$\endgroup$
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.

$\endgroup$
  • $\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 '10 at 4:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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