**
How Hard Is Counting Triangles in the Streaming Model?
**

*
Vladimir Braverman,
Rafail Ostrovsky,
Dan Vilenchik
*

**
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.
Specifically, 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. If a constant number of passes is allowed, we show a 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 p(G)-the triangle density, and conjecture that the space complexity of the triangles problem is Θ(m/p(G)).
We match this by a second algorithm that solves the distinguishing problem using O(m/p(G))-memory.

**comment:**
ICALP 2013 pp: 244-254

Fetch PDF file of the paper

Back to Publications List |