License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2017.11
URN: urn:nbn:de:0030-drops-70222
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7022/
Go to the corresponding LIPIcs Volume Portal

Bera, Suman K. ; Chakrabarti, Amit

Towards Tighter Space Bounds for Counting Triangles and Other Substructures in Graph Streams

pdf-format:
LIPIcs-STACS-2017-11.pdf (0.6 MB)

Abstract

We revisit the much-studied problem of space-efficiently estimating the number of triangles in a graph stream, and extensions of this problem to counting fixed-sized cliques and cycles. For the important special case of counting triangles, we give a 4-pass, (1 +/- epsilon)-approximate, randomized algorithm using O-tilde(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 multi-pass 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 multi-pass 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 cash-register 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 triangle-counting 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:1--11:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-028-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{66},
  editor =	{Heribert Vollmer and Brigitte Vallée},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7022},
  URN =		{urn:nbn:de:0030-drops-70222},
  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

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI