finding c4s

Theorem

Let be the number of C4s in your graph. There is a C4 detection algorithm with the following guarantees: If C4 exists, outputs yes with high probability. If C4 not exists outputs no. If the running time is . O/w running time is .

Some notes: WMA maxdegree average degree . Because degree profile of -free graph looks nice.

The second fast algorithm is by BFSing out of vertices in a random order until we find a C4. The first fast algorithm is by subsampling the vertices. We needed to be big to have reasonable variance here.