Improved 3-pass Algorithm for Counting 4-cycles in Arbitrary Order Streaming

07/27/2020

∙

by   Sofya Vorotnikova, et al.

∙

0

∙

share

The problem of counting small subgraphs, and specifically cycles, in the streaming model received a lot of attention over the past few years. In this paper, we consider arbitrary order insertion-only streams, improving over the state-of-the-art result on counting 4-cycles. Our algorithm computes a (1+ϵ)-approximation by taking three passes over the stream and using space O(m log n/ϵ^2 T^1/3), where m is the number of edges in the graph and T is the number of 4-cycles.