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.

Improve this question
$\endgroup$
3

2 Answers 2

Reset to default
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.

Improve this answer
$\endgroup$
0
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})$.

Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ This is great! I really appreciate it. :) $\endgroup$
    – Michael Wehar
    Commented Nov 6, 2015 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
    Commented Nov 6, 2015 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
    Commented Nov 6, 2015 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
    Commented Nov 6, 2015 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
    Commented Nov 6, 2015 at 15:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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