Near-Optimal Four-Cycle Counting in Graph Streams

Abstract

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/\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 $\hat{I}\text{c◯}(m/\sqrt{T})$ by McGregor and Vorotnikova.

SODA 2026