2014/01/09 by Graham Cormode, Cormode, Graham, Hossein Jowhari +1 · 1 citation
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.1401.2175
openalex publication_date 2014/01/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper we present improved results on the problem of counting triangles in edge streamed graphs. For graphs with m edges and at least T triangles, we show that an extra look over the stream yields a two-pass treaming algorithm that uses O(\fracm\eps2.5√(T)\polylog(m)) space and outputs a (1+\eps) approximation of the number of triangles in the graph. This improves upon the two-pass streaming tester of Braverman, Ostrovsky and Vilenchik, ICALP 2013, which distinguishes between triangle-free graphs and graphs with at least T triangle using O(\fracmT1/3) space. Also, in terms of dependence on T, we show that more passes would not lead to a better space bound. In other words, we prove there is no constant pass streaming algorithm that distinguishes between triangle-free graphs from graphs with at least T triangles using O(\fracmT1/2+ρ) space for any constant ρ≥ 0.