Near-Optimal Four-Cycle Counting in Graph Streams

Sebastian Lüderssen, Stefan Neumann, Pan Peng

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 $\widetilde{O}(m/\s…