How hard is counting triangles in the streaming model?

DOI10.1007/978-3-642-39206-1_21MaRDI QIDQ5326565zbMATH OpenOpenAlexFDO

Authors Vladimir Braverman, Rafail Ostrovsky, Dan Vilenchik

Publication date 6 August 2013

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

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

Mathematics Subject Classification ID

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

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.

Recommendations

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

Cited in

(20)

• FURL: fixed-memory and uncertainty reducing local triangle counting for multigraph streams
• A second look at counting triangles in graph streams (corrected)
• Corrigendum to: ``A second look at counting triangles in graph streams
• Approximate counting of cycles in streams
• Counting arbitrary subgraphs in data streams
• Colorful triangle counting and a \textsc{MapReduce} implementation
• A hybrid sampling scheme for triangle counting
• scientific article; zbMATH DE number 2119719 (Why is no real title available?)
• A Simple Sublinear-Time Algorithm for Counting Arbitrary Subgraphs via Edge Sampling
• On Estimating Path Aggregates over Streaming Graphs
• Computing and Combinatorics
• Efficient triangle counting in large graphs via degree-based vertex partitioning
• Efficient triangle counting in large graphs via degree-based vertex partitioning
• Counting simplices in hypergraph streams
• Towards optimal dynamic indexes for approximate (and exact) triangle counting
• Maximum coverage in the data stream model: parameterized and generalized
• Near uniform triangle sampling over adjacency list graph streams
• A second look at counting triangles in graph streams
• On triangle estimation using tripartite independent set queries
• Main-memory triangle computations for very large (sparse (power-law)) graphs

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)