How hard is counting triangles in the streaming model?

DOI10.1007/978-3-642-39206-1_21zbMATH Open1336.68283arXiv1304.1458OpenAlexW1799685217MaRDI QIDQ5326565FDOQ5326565

Authors: Vladimir Braverman, Rafail Ostrovsky, Dan Vilenchik 

Publication date: 6 August 2013

Published in: Automata, Languages, and Programming (Search for Journal in Brave)

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 $Omega(m)$ for graphs $G$ with $m$ edges on $n$ vertices. If a constant number of passes is allowed, we show a lower bound of $Omega(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 $ho(G)$ -- the triangle density, and conjecture that the space complexity of the triangles problem is $Omega(m/ho(G))$. We match this by a second algorithm that solves the distinguishing problem using $O(m/ho(G))$-memory.

Full work available at URL: https://arxiv.org/abs/1304.1458

Recommendations

• A second look at counting triangles in graph streams
• Computing and Combinatorics
• scientific article; zbMATH DE number 6862103
• Triangle counting in dynamic graph streams
• A hybrid sampling scheme for triangle counting

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Enumeration in graph theory (05C30)

Cited In (14)

• A second look at counting triangles in graph streams (corrected)
• Main-memory triangle computations for very large (sparse (power-law)) graphs
• A hybrid sampling scheme for triangle counting
• Efficient triangle counting in large graphs via degree-based vertex partitioning
• Title not available (Why is that?)
• On Estimating Path Aggregates over Streaming Graphs
• Computing and Combinatorics
• A Simple Sublinear-Time Algorithm for Counting Arbitrary Subgraphs via Edge Sampling
• Colorful triangle counting and a \textsc{MapReduce} implementation
• Corrigendum to: ``A second look at counting triangles in graph streams
• Efficient triangle counting in large graphs via degree-based vertex partitioning
• A second look at counting triangles in graph streams
• Approximate counting of cycles in streams
• Counting arbitrary subgraphs in data streams

This page was built for publication: How hard is counting triangles in the streaming model?

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5326565)