Abstract
We revisit the muchstudied problem of spaceefficiently estimating the number of triangles in a graph stream, and extensions of this problem to counting fixedsized cliques and cycles. For the important special case of counting triangles, we give a 4pass, (1 +/ epsilon)approximate, randomized algorithm using Otilde(epsilon^(2) m^(3/2) / T) space, where m is the number of edges and T is a promised lower bound on the number of triangles. This matches the space bound of a recent algorithm (McGregor et al., PODS 2016), with an arguably simpler and more general technique. We give an improved multipass lower bound of Omega(min{m^(3/2)/T , m/sqrt(T)}), applicable at essentially all densities Omega(n) <= m <= O(n^2). We prove other multipass lower bounds in terms of various structural parameters of the input graph. Together, our results resolve a couple of open questions raised in recent work (Braverman et al., ICALP 2013).
Our presentation emphasizes more general frameworks, for both upper and lower bounds. We give a sampling algorithm for counting arbitrary subgraphs and then improve it via combinatorial means in the special cases of counting odd cliques and odd cycles. Our results show that these problems are considerably easier in the cashregister streaming model than in the turnstile model, where previous work had focused. We use Turán graphs and related gadgets to derive lower bounds for counting cliques and cycles, with trianglecounting lower bounds following as a corollary.
BibTeX  Entry
@InProceedings{bera_et_al:LIPIcs:2017:7022,
author = {Suman K. Bera and Amit Chakrabarti},
title = {{Towards Tighter Space Bounds for Counting Triangles and Other Substructures in Graph Streams}},
booktitle = {34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)},
pages = {11:111:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770286},
ISSN = {18688969},
year = {2017},
volume = {66},
editor = {Heribert Vollmer and Brigitte Vallée},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7022},
URN = {urn:nbn:de:0030drops70222},
doi = {10.4230/LIPIcs.STACS.2017.11},
annote = {Keywords: data streaming, graph algorithms, triangles, subgraph counting, lower bounds}
}
Keywords: 

data streaming, graph algorithms, triangles, subgraph counting, lower bounds 
Collection: 

34th Symposium on Theoretical Aspects of Computer Science (STACS 2017) 
Issue Date: 

2017 
Date of publication: 

06.03.2017 