In 1994, Yuster and Zwick [1]} put forth the conjecture that one cannot detect a 4-cycle in a graph in subquadratic time.
The longstanding upper bound is \(O(m^{4/3})\)  via a high-degree low-degree argument
[2]}. The running time can also be bounded by \(O(n^2)\)  because when \(m \ge 200\cdot n^{1.5}\)  we can simply output “yes”: by the Bondy-Simonovitz Theorem [3]}, a graph with such density must contain a 4-cycle.
Frustratingly, to this date, the field of fine-grained complexity has not managed to show any hardness for this problem.
“What hope do we have to
understand more complex problems if we cannot settle the complexity of this simple one, even
conditionally?”This is a quote from the survey by Rubinstein and Vassilevska Williams [4]} where it is referring to the approximability of the graph diameter problem. We find it no less poignant when considering the 4-cycle problem.
