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

Question

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.

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, Nov 06 '15 at 04:34
Additional info can be found in this paper: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.94.8121 — Michael Wehar, Nov 06 '15 at 04:51
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. (In case you weren't already aware of it). — Juho, Nov 06 '15 at 14:01

score 29 · Accepted Answer · answered Nov 07 '15 at 23:07

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.

score 13 · Answer 2 · answered Nov 06 '15 at 06:48

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

answered Nov 06 '15 at 06:48

David Eppstein

50,990
3
170
278

1

This is great! I really appreciate it. :) – Michael Wehar Nov 06 '15 at 07:35
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 Nov 06 '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: http://www.sciencedirect.com/science/article/pii/S0012365X99901073 – Michael Wehar Nov 06 '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 06 '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 06 '15 at 15:36

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

2 Answers2