A Truly Subcubic Combinatorial Algorithm for Induced 4-Cycle Detection

Amir Abboud, Shyan Akmal, Nick Fischer

We present the first truly subcubic, combinatorial algorithm for detecting an induced $4$-cycle in a graph. The running time is $O(n^{2.84})$ on $n$-node graphs, thus separating th…