15
$\begingroup$

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.

$\endgroup$
29
$\begingroup$

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.

$\endgroup$
13
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.