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+\epsilon )$-approximating the number of four-cycles using $\tilde{O}(m\mathrm{/}\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\mathrm{/}{T}^{1\mathrm{/}3})$ and matches a multi-pass lower bound of $\mathrm{\Omega }(m\mathrm{/}\sqrt{T})$ by McGregor and Vorotnikova.