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 + \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.
Fields of Study & Subjects
Markov Chains and Monte Carlo Methods
Complexity and Algorithms in Graphs
Algorithms and Data Compression
Publication details
- Journal / source
- Society for Industrial and Applied Mathematics eBooks
- Publisher
- Society for Industrial and Applied Mathematics
- Pages
- 4285–4326
- Publication date
- 1 January 2026
- Language
- EN