How Hard is Counting Triangles in the Streaming Model

2013/04/04 by Braverman, Vladimir, Ostrovsky, Rafail, Vilenchik, Dan · 1 citation
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1304.1458

Abstract

The problem of (approximately) counting the number of triangles in a graph is one of the basic problems in graph theory. In this paper we study the problem in the streaming model. We study the amount of memory required by a randomized algorithm to solve this problem. In case the algorithm is allowed one pass over the stream, we present a best possible lower bound of Ω(m) for graphs G with m edges on n vertices. If a constant number of passes is allowed, we show a lower bound of Ω(m/T), T the number of triangles. We match, in some sense, this lower bound with a 2-pass O(m/T^1/3)-memory algorithm that solves the problem of distinguishing graphs with no triangles from graphs with at least T triangles. We present a new graph parameter ρ(G) -- the triangle density, and conjecture that the space complexity of the triangles problem is Ω(m/ρ(G)). We match this by a second algorithm that solves the distinguishing problem using O(m/ρ(G))-memory.

Cited by

• Testable algorithms for approximately counting edges and triangles in sublinear time and space

Related

• An Optimal Algorithm for Triangle Counting in the Stream
• A Second Look at Counting Triangles in Graph Streams (revised)
• How the Degeneracy Helps for Triangle Counting in Graph Streams
• Parallel Triangle Counting in Massive Streaming Graphs
• Triangle counting in dynamic graph streams