<p>It's not quadratic, but Alon Yuster and Zwick ("Finding and counting given length cycles", <em>Algorithmica</em> 1997) give an algorithm for finding triangles in time $O(m^{2\omega/(\omega+1)})$, where $\omega$ is the exponent for fast matrix multiplication. For 4-cycle-free graphs, plugging in $\omega&lt;2.373$ and $m=O(n^{3/2})$ (else there is a $4$-cycle regardless of existence of $3$-cycles) gives time $O(n^{3\omega/(\omega+1)})=O(n^{2.111})$.</p>

CC BY-SA 3.0
2015-11-06T07:35:07.413Z
This is great!  I really appreciate it.  :)
Michael Wehar
CC BY-SA 3.0
2015-11-06T15:12:17.280Z
Yep, if a graph has no 4-cycles, then it has at most $O(n^{\frac{3}{2}})$ edges.  Link: https://books.google.com/books?id=NV3Y8vjWo8kC&pg=PA25&lpg=PA25&dq=Reiman+1958+4-cycle+free+graphs&source=bl&ots=SNaP0lMEg3&sig=oCNaJf8UFCCdjDTMaJWh0stsJD8&hl=en&sa=X&ved=0CDMQ6AEwA2oVChMI38Pfpor8yAIVyxgeCh10zQis#v=onepage&q=Reiman%201958%204-cycle%20free%20graphs&f=false
Michael Wehar
CC BY-SA 3.0
2015-11-06T15:25:17.763Z
Feel free to correct me if I'm wrong.  It seems that "The Even Circuit Theorem" by Erdos says that if a graph is $2k$-cycle free, then it has at most $O(n^{1+\frac{1}{k}})$ edges.  Link: http://www.sciencedirect.com/science/article/pii/S0012365X99901073
Michael Wehar
CC BY-SA 3.0
2015-11-06T15:33:02.693Z
As a result, if a graph has no 6 cycle, then it has at most $O(n^{\frac{4}{3}})$ edges.  Therefore, we can determine if it has a 3-cycle in $O(n^{1.876})$ time using the method that David suggested.  :)
Michael Wehar
CC BY-SA 3.0
2015-11-06T15:36:16.953Z
Further, for any fixed $k > 2$, if $G$ is $2k$-cycle free, then we can determine if $G$ has a 3-cycle in subquadratic time because $G$ doesn't have too many edges.  However, when $k = 2$, that's when things get interesting.  Can we beat $O(n^{2.111})$?
Michael Wehar
CC BY-SA 3.0
2015-11-06T06:48:42.950Z
2015-11-06T06:48:42.950Z
David Eppstein
<p>Yes, this is known. It appears in one of the must-cite references on triangle finding...</p>

<p>Namely, Itai and Rodeh show in SICOMP 1978 how to find, in $O(n^2)$ time, a cycle in a graph that has at most one more edge than the minimum length cycle. (See the first three sentences of the abstract here: <a href="http://www.cs.technion.ac.il/~itai/publications/Algorithms/min-circuit.pdf">http://www.cs.technion.ac.il/~itai/publications/Algorithms/min-circuit.pdf</a>) It is a simple procedure based on properties of breadth-first search.</p>

<p>So, if your graph is 4-cycle free and there is a triangle, their algorithm must output it, because it cannot output a 5-cycle or larger.</p>

CC BY-SA 3.0
2015-11-07T23:07:48.090Z
2015-11-07T23:07:48.090Z
Ryan Williams
<p>The $k$-cycle problem is as follows:</p>

<p><strong>Instance:</strong> An undirected graph $G$ with $n$ vertices and up to $n \choose 2$ edges.</p>

<p><strong>Question:</strong> Does there exist a (proper) $k$-cycle in $G$?</p>

<p><strong>Background:</strong> For any fixed $k$, we can solve $2k$-cycle in $O(n^2)$ time.</p>

<blockquote>
  <p><a href="http://epubs.siam.org/doi/abs/10.1137/S0895480194274133?journalCode=sjdmec">Raphael Yuster, Uri Zwick: Finding Even Cycles Even Faster. SIAM J. <br> Discrete Math. 10(2): 209-222 (1997)</a></p>
</blockquote>

<p>However, it is not known if we can solve 3-cycle (i.e. 3-clique) in less than matrix multiplication time.</p>

<p><strong>My Question:</strong> Assuming that $G$ contains no 4-cycles, can we solve the 3-cycle problem in $O(n^2)$ time?</p>

<p>David suggested an approach for solving this variant of the 3-cycle problem in $O(n^{2.111})$ time.</p>

CC BY-SA 3.0
2015-11-06T04:34:03.700Z
It seems that if a graph $G$'s smallest cycle has length at least 5, then it has at most $O(n^{\frac{3}{2}})$ edges.  Link: http://link.springer.com/article/10.1007%2FBF01787638
Michael Wehar
CC BY-SA 3.0
2015-11-06T04:51:40.873Z
Additional info can be found in this paper: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.94.8121
Michael Wehar
CC BY-SA 3.0
2015-11-06T14:01:14.097Z
I think you might also be interested in [Eisenbrand, Friedrich, and Fabrizio Grandoni. "On the complexity of fixed parameter clique and dominating set." Theoretical Computer Science 326.1 (2004): 57-67.](http://www.sciencedirect.com/science/article/pii/S030439750400372X) (In case you weren't already aware of it).
Juho
<graph-theory><graph-algorithms><clique><polynomial-time><fixed-parameter-tractable>
Given a 4-cycle free graph $G$, can we determine if it has a 3-cycle in quadratic time?
Michael Wehar
# Given a 4-cycle free graph $G$, can we determine if it has a 3-cycle in quadratic time?

(Asked by: username_0 on 2015-11-06)

The $k$-cycle problem is as follows:

**Instance:** An undirected graph $G$ with $n$ vertices and up to $n \choose 2$ edges.

**Question:** Does there exist a (proper) $k$-cycle in $G$?

**Background:** For any fixed $k$, we can solve $2k$-cycle in $O(n^2)$ time.

> [Raphael Yuster, Uri Zwick: Finding Even Cycles Even Faster. SIAM J.   
>  Discrete Math. 10(2): 209-222 (1997)](http://epubs.siam.org/doi/abs/10.1137/S0895480194274133?journalCode=sjdmec)

However, it is not known if we can solve 3-cycle (i.e. 3-clique) in less than matrix multiplication time.

**My Question:** Assuming that $G$ contains no 4-cycles, can we solve the 3-cycle problem in $O(n^2)$ time?

David suggested an approach for solving this variant of the 3-cycle problem in $O(n^{2.111})$ time.

**Tags:** graph-theory, graph-algorithms, clique, polynomial-time, fixed-parameter-tractable
> **Comments:**
> **username_0**: It seems that if a graph $G$'s smallest cycle has length at least 5, then it has at most $O(n^{\frac{3}{2}})$ edges.  Link: http://link.springer.com/article/10.1007%2FBF01787638  
> **username_0**: Additional info can be found in this paper: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.94.8121  
> **username_1**: I think you might also be interested in [Eisenbrand, Friedrich, and Fabrizio Grandoni. "On the complexity of fixed parameter clique and dominating set." Theoretical Computer Science 326.1 (2004): 57-67.](http://www.sciencedirect.com/science/article/pii/S030439750400372X) (In case you weren't already aware of it).  

---

## 2 answers

### Answer by username_3 on 2015-11-07. Score: 29 | Accepted answer

Yes, this is known. It appears in one of the must-cite references on triangle finding...

Namely, Itai and Rodeh show in SICOMP 1978 how to find, in $O(n^2)$ time, a cycle in a graph that has at most one more edge than the minimum length cycle. (See the first three sentences of the abstract here: <http://www.cs.technion.ac.il/~itai/publications/Algorithms/min-circuit.pdf>) It is a simple procedure based on properties of breadth-first search.

So, if your graph is 4-cycle free and there is a triangle, their algorithm must output it, because it cannot output a 5-cycle or larger.


---

### Answer by username_2 on 2015-11-06. Score: 13

It's not quadratic, but Alon Yuster and Zwick ("Finding and counting given length cycles", *Algorithmica* 1997) give an algorithm for finding triangles in time $O(m^{2\omega/(\omega+1)})$, where $\omega$ is the exponent for fast matrix multiplication. For 4-cycle-free graphs, plugging in $\omega<2.373$ and $m=O(n^{3/2})$ (else there is a $4$-cycle regardless of existence of $3$-cycles) gives time $O(n^{3\omega/(\omega+1)})=O(n^{2.111})$.

> **Comments:**
> **username_0**: This is great!  I really appreciate it.  :)  
> **username_0**: Yep, if a graph has no 4-cycles, then it has at most $O(n^{\frac{3}{2}})$ edges.  Link: https://books.google.com/books?id=NV3Y8vjWo8kC&pg=PA25&lpg=PA25&dq=Reiman+1958+4-cycle+free+graphs&source=bl&ots=SNaP0lMEg3&sig=oCNaJf8UFCCdjDTMaJWh0stsJD8&hl=en&sa=X&ved=0CDMQ6AEwA2oVChMI38Pfpor8yAIVyxgeCh10zQis#v=onepage&q=Reiman%201958%204-cycle%20free%20graphs&f=false  
> **username_0**: Feel free to correct me if I'm wrong.  It seems that "The Even Circuit Theorem" by Erdos says that if a graph is $2k$-cycle free, then it has at most $O(n^{1+\frac{1}{k}})$ edges.  Link: http://www.sciencedirect.com/science/article/pii/S0012365X99901073  
> **username_0**: As a result, if a graph has no 6 cycle, then it has at most $O(n^{\frac{4}{3}})$ edges.  Therefore, we can determine if it has a 3-cycle in $O(n^{1.876})$ time using the method that David suggested.  :)  
> **username_0**: Further, for any fixed $k > 2$, if $G$ is $2k$-cycle free, then we can determine if $G$ has a 3-cycle in subquadratic time because $G$ doesn't have too many edges.  However, when $k = 2$, that's when things get interesting.  Can we beat $O(n^{2.111})$?  

---

