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

<p>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. </p>

CC BY-SA 2.5
2010-12-16T04:45:11.977Z
Thank you!  I will take a look at the Monien paper when I can get access to it.
Andrew D. King
CC BY-SA 2.5
2010-12-15T19:59:34.043Z
2010-12-15T20:08:28.870Z
2010-12-15T20:08:28.870Z
Mihai
<p>To add to Mihai's answer:</p>

<p>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:</p>

<p><a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.101.4120">http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.101.4120</a></p>

<p>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. </p>

<p>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.</p>

CC BY-SA 2.5
2010-12-16T20:49:00.707Z
2010-12-16T21:40:49.103Z
2010-12-16T21:40:49.103Z
Ryan Williams
<p>(crossposted from MathOverflow)</p>

<p>Hi,</p>

<p>I was reading this thread: <a href="https://mathoverflow.net/questions/16393/finding-a-cycle-of-fixed-length">https://mathoverflow.net/questions/16393/finding-a-cycle-of-fixed-length</a></p>

<p>I want to find a 5-cycle in a graph.  Actually, what I <em>really</em> 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.  </p>

<p>Can we do better than colour coding for finding a 5-cycle in this case?  Let me give a specific formulation of my question:</p>

<blockquote>
  <p>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?</p>
</blockquote>

CC BY-SA 2.5
2010-12-14T07:23:18.140Z
[Crosspost](http://mathoverflow.net/questions/49356/finding-a-5-cycle-in-a-sparse-graph-efficiently) from MO.
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2010-12-14T15:07:35.450Z
Do your graphs have any special structure, other than being sparse? (Such as low degeneracy, for example.)
Robin Kothari
CC BY-SA 2.5
2010-12-14T17:46:02.227Z
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
CC BY-SA 2.5
2010-12-14T21:28:46.680Z
To be clear, you don't mind if the cycle contains repeated vertices, correct?
user834
CC BY-SA 2.5
2010-12-15T15:04:13.777Z
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
<ds.algorithms><graph-theory><graph-algorithms><sparse-matrix>
Finding a 5-cycle in a sparse graph efficiently.
Andrew D. King
# Finding a 5-cycle in a sparse graph efficiently.

(Asked by: username_0 on 2010-12-14)

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

**Tags:** ds.algorithms, graph-theory, graph-algorithms, sparse-matrix
> **Comments:**
> **username_1**: [Crosspost](http://mathoverflow.net/questions/49356/finding-a-5-cycle-in-a-sparse-graph-efficiently) from MO.  
> **username_2**: Do your graphs have any special structure, other than being sparse? (Such as low degeneracy, for example.)  
> **username_0**: 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)|$.  
> **username_3**: To be clear, you don't mind if the cycle contains repeated vertices, correct?  
> **username_0**: 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.  

---

## 2 answers

### Answer by username_5 on 2010-12-16. Score: 21 | Accepted answer

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.


---

### Answer by username_4 on 2010-12-15. Score: 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.

> **Comments:**
> **username_0**: Thank you!  I will take a look at the Monien paper when I can get access to it.  

---

