A second look at counting triangles in graph streams

DOI10.1016/J.TCS.2014.07.025MaRDI QIDQ740973zbMATH OpenOpenAlexFDO

Authors Graham Cormode, Hossein Jowhari

Publication date 10 September 2014

Published in Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

data streamsgraphsrandomized algorithms

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20)

Abstract: 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(fracmep{s}^{2.5}sqrtTpolylog(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(fracm{T}^{1/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(fracm{T}^{1/2+ho})$ space for any constant $hoge0$.

Recommendations

• A second look at counting triangles in graph streams (corrected)
• How hard is counting triangles in the streaming model?
• Computing and Combinatorics
• scientific article; zbMATH DE number 6862103

Cites work

• Colorful triangle counting and a \textsc{MapReduce} implementation
• Communication Complexity
• Computing and Combinatorics
• Experimental and Efficient Algorithms
• How hard is counting triangles in the streaming model?
• scientific article; zbMATH DE number 2019620 (Why is no real title available?)
• scientific article; zbMATH DE number 2119719 (Why is no real title available?)
• scientific article; zbMATH DE number 819814 (Why is no real title available?)
• Stream Order and Order Statistics: Quantile Estimation in Random-Order Streams

Cited in

(12)

• New bounds for the CLIQUE-GAP problem using graph decomposition theory
• Summarized bit batch-based triangle listing in massive graphs
• A second look at counting triangles in graph streams (corrected)
• Corrigendum to: ``A second look at counting triangles in graph streams
• New bounds for the CLIQUE-GAP problem using graph decomposition theory
• scientific article; zbMATH DE number 6862103 (Why is no real title available?)
• scientific article; zbMATH DE number 2119719 (Why is no real title available?)
• Counting Triangles under Updates in Worst-Case Optimal Time
• How hard is counting triangles in the streaming model?
• Computing and Combinatorics
• Counting simplices in hypergraph streams
• Near uniform triangle sampling over adjacency list graph streams

Describes a project that uses

Uses Software

• DOULION

This page was built for publication: A second look at counting triangles in graph streams

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