Near-Optimal Four-Cycle Counting in Graph Streams
This provides a near-optimal solution for four-cycle counting in graph streams, which is important for applications in network analysis and streaming algorithms.
The paper tackles the problem of approximating the number of four-cycles in graph streams, presenting a 3-pass algorithm that achieves a (1+ε)-approximation using space Õ(m/√T), which improves upon prior work and matches a known lower bound.
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 $\widetilde{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 $\widetilde{O}(m/T^{1/3})$ and matches a multi-pass lower bound of $Ω(m/\sqrt{T})$ by McGregor and Vorotnikova.