An Optimal Algorithm for Triangle Counting in the Stream

2021/05/04 by Jayaram, Rajesh, Kallaugher, John · 1 citation
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2105.01785

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: \widetildeO((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.

Cited by

• Robust Streaming Against Low-Memory Adversaries

Related

• How Hard is Counting Triangles in the Streaming Model
• A Second Look at Counting Triangles in Graph Streams (revised)
• How the Degeneracy Helps for Triangle Counting in Graph Streams
• Triangle counting in dynamic graph streams
• A Hybrid Sampling Scheme for Triangle Counting