Near-Optimal Four-Cycle Counting in Graph Streams

We study four-cycle counting in arbitrary order graph streams. We present a 3-pass algorithm for $(1 + \varepsilon)$-approximating the number of four-cycles using $\tilde O(m/\sqrt T)$ space, where $m$ is the number of edges and $T$ the number of four-cycles in the graph. This improves upon a 3-pass algorithm by Vorotnikova using space $\tilde O(m/T^{1/3})$ and matches a multi-pass lower bound of $\Omega(m/\sqrt T)$ by McGregor and Vorotnikova.