The beta version of DROPS 2 is now publicly available! Check this page out at DROPS 2 now!


License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2021.11
URN: urn:nbn:de:0030-drops-147046
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14704/
Go to the corresponding LIPIcs Volume Portal

Jayaram, Rajesh ; Kallaugher, John

An Optimal Algorithm for Triangle Counting in the Stream

pdf-format:
LIPIcs-APPROX11.pdf (0.6 MB)

Abstract

We present a new algorithm for approximating the number of triangles in a graph G whose edges arrive as an arbitrary order stream. If m is the number of edges in G, T the number of triangles, Δ_E the maximum number of triangles which share a single edge, and Δ_V the maximum number of triangles which share a single vertex, then our algorithm requires space:
Õ(m/T⋅(Δ_E + √{Δ_V}))
Taken with the Ω((m Δ_E)/T) lower bound of Braverman, Ostrovsky, and Vilenchik (ICALP 2013), and the Ω((m √{Δ_V})/T) lower bound of Kallaugher and Price (SODA 2017), our algorithm is optimal up to log factors, resolving the complexity of a classic problem in graph streaming.

BibTeX - Entry

@InProceedings{jayaram_et_al:LIPIcs.APPROX/RANDOM.2021.11,
  author =	{Jayaram, Rajesh and Kallaugher, John},
  title =	{{An Optimal Algorithm for Triangle Counting in the Stream}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)},
  pages =	{11:1--11:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-207-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{207},
  editor =	{Wootters, Mary and Sanit\`{a}, Laura},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/14704},
  URN =		{urn:nbn:de:0030-drops-147046},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2021.11},
  annote =	{Keywords: Triangle Counting, Streaming, Graph Algorithms, Sampling, Sketching}
}

Keywords: Triangle Counting, Streaming, Graph Algorithms, Sampling, Sketching
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)
Issue Date: 2021
Date of publication: 15.09.2021

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