Four-Cycle Counting in Low-Degeneracy Graph Streams (opens in new tab)

We study the problem of $(1+\varepsilon)$-approximating the number of four-cycles in graphs given as arbitrary order edge streams. We propose two new algorithms based on sampling induced subgraphs. Our first contribution is a two-pass algorithm that uses $\widetilde{O}(\kappa m / \sqrt{T})$ space, where $m$ is the number of edges, $T$ is the number of four-cycles, and $\kappa$ is the graph's degeneracy. This algorithm improves upon existing theo...