Triangle and Four Cycle Counting in the Data Stream Model

The problem of estimating the number of cycles in a graph is one of the most widely studied graph problems in the data stream model. Three relevant variants of the data stream model include: the arbitrary order model in which the stream consists of the edges of the graph in arbitrary order, the random order model in which the edges are randomly permuted, and the adjacency list order model in which all edges incident to the same vertex appear consecutively. In this paper, we focus on the problem of triangle and four-cycle counting in these models. We improve over the state-of-the-art results as follows, where n is the number of vertices, m is the number of edges and T is the number of triangles/four-cycles in the graph (i.e., the quantity being estimated): Random Order Model: We present a single-pass algorithm that (1 + epsilon)-approximates the number of triangles using (O) over tilde (c(-2)m/root T) space and prove that this is optimal in the range T <= root m. The best previous result, a (3 + epsilon)-approximation using (O) over tilde(epsilon(-4.5)m/root T) space, was presented by Cormode and Jowhari (Theor. Comput. Sci. 2017). Adjacency List Model: We present an algorithm that returns a (1 + epsilon)-approximation of the number of 4-cycles using two passes and (O) over tilde(epsilon(-4)m/root T) space. The best previous result, a constant approximation using e O(m/T 3/8) space, was presented by Kallaugher et al. (PODS 2019). We also show that (1 +epsilon)-approximation in a single pass is possible in a) polylog( n) space if T = Omega(n(2)) and b) (O) over tilde (n) space if T = Omega(n). Arbitrary Order Model: We present a three-pass algorithm that (1 + epsilon)-approximates the number of 4-cycles using e O(.-2m/ T 1/4) space and a one-pass algorithm that uses (O) over tilde(epsilon(-2)n) space when T = (O) over tilde (n(2)). The best existing result, a (1 + epsilon)-approximation using (O) over tilde(epsilon(-2)m(2) /T) space, was presented by Bera and Chakrabarti (STACS 2017). We also show a multi-pass lower bound and another algorithm for distinguishing graphs with no four cycles and graphs with many 4-cycles.