21

(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?

Community
  • 1
Andrew D. King
  • 1,573
  • 10
  • 19
  • 3
    Crosspost from MO. – Hsien-Chih Chang 張顯之 Dec 14 '10 at 07:23
  • Do your graphs have any special structure, other than being sparse? (Such as low degeneracy, for example.) – Robin Kothari Dec 14 '10 at 15:07
  • 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)|$. – Andrew D. King Dec 14 '10 at 17:46
  • To be clear, you don't mind if the cycle contains repeated vertices, correct? – user834 Dec 14 '10 at 21:28
  • 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. – Andrew D. King Dec 15 '10 at 15:04

2 Answers2

21

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.

Ryan Williams
  • 27,465
  • 7
  • 115
  • 164
13

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.

Mihai
  • 1,870
  • 13
  • 14