An Optimal Algorithm for Triangle Counting in the Stream

DOI10.4230/LIPICS.APPROX/RANDOM.2021.11MaRDI QIDQ6090881zbMATH OpenOpenAlexFDO

Authors Rajesh Jayaram, John Kallaugher

Publication date 20 November 2023

Full work available at URL https://arxiv.org/abs/2105.01785

zbMATH Keywords

graph algorithmssamplingsketchingstreamingtriangle counting

Mathematics Subject Classification ID

Randomized algorithms (68W20) Approximation algorithms (68W25) Combinatorial optimization (90C27)

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, $Delt{a}_E$ the maximum number of triangles which share a single edge, and $Delt{a}_V$ the maximum number of triangles which share a single vertex, then our algorithm requires space: [ widetilde{O}left(frac{m}{T}cdot left(Delta_E + sqrt{Delta_V} ight) ight) ] Taken with the $Omegaleft(fracmDelt{a}_{E}Tight)$ lower bound of Braverman, Ostrovsky, and Vilenchik (ICALP 2013), and the $Omegaleft(fracmsqrtDelt{a}_{V}Tight)$ 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.

Cited in

(5)

• scientific article; zbMATH DE number 6862103 (Why is no real title available?)
• Counting Triangles under Updates in Worst-Case Optimal Time
• Listing 4-cycles
• Counting simplices in hypergraph streams
• Near uniform triangle sampling over adjacency list graph streams

This page was built for publication: An Optimal Algorithm for Triangle Counting in the Stream

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6090881)