# An Optimal Algorithm for Triangle Counting in the Stream

arXiv: https://arxiv.org/abs/2105.01785 · HTML: https://mlsanity.com/paper/2105.01785/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 May 2021.

## Built on by (most cited first, 2 of 2)

- [Triangle and Four Cycle Counting with Predictions in Graph Streams](https://mlsanity.com/paper/2203.09572/) (2022)
- [Fast and Accurate Triangle Counting in Graph Streams Using Predictions](https://mlsanity.com/paper/2409.15205/) (2024)

## Abstract (arXiv)

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, DeltaE the maximum number of triangles which share a single edge, and DeltaV the maximum number of triangles which share a single vertex, then our algorithm requires space: [ widetildeOleft(fracmT· left(DeltaE + √DeltaVright)right) ] Taken with the Omegaleft(fracm DeltaETright) lower bound of Braverman, Ostrovsky, and Vilenchik (ICALP 2013), and the Omegaleft( fracm √DeltaVTright) 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.