# Given a 4-cycle free graph $G$, can we determine if it has a 3-cycle in quadratic time?

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)

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.

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.

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})$.

• This is great! I really appreciate it. :) – Michael Wehar Nov 6 '15 at 7:35
• Yep, if a graph has no 4-cycles, then it has at most $O(n^{\frac{3}{2}})$ edges. Link: books.google.com/… – Michael Wehar Nov 6 '15 at 15:12
• 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: sciencedirect.com/science/article/pii/S0012365X99901073 – Michael Wehar Nov 6 '15 at 15:25
• 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 Nov 6 '15 at 15:33
• 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 Nov 6 '15 at 15:36