A second look at counting triangles in graph streams

DOI10.1016/J.TCS.2014.07.025zbMATH Open1370.68119arXiv1401.2175OpenAlexW2084170146MaRDI QIDQ740973FDOQ740973

Hossein Jowhari, Graham Cormode

Publication date: 10 September 2014

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

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$.

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

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
• Triangle counting in dynamic graph streams

zbMATH Keywords

graphsrandomized algorithmsdata streams

Mathematics Subject Classification ID

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

Cites Work

• Communication Complexity
• Title not available (Why is that?)
• Title not available (Why is that?)
• Colorful triangle counting and a \textsc{MapReduce} implementation
• Computing and Combinatorics
• Stream Order and Order Statistics: Quantile Estimation in Random-Order Streams
• Title not available (Why is that?)
• Experimental and Efficient Algorithms
• How Hard Is Counting Triangles in the Streaming Model?

Cited In (8)

• Counting Triangles under Updates in Worst-Case Optimal Time
• Summarized bit batch-based triangle listing in massive graphs
• Title not available (Why is that?)
• Computing and Combinatorics
• Title not available (Why is that?)
• New Bounds for the CLIQUE-GAP Problem Using Graph Decomposition Theory
• Triangle counting in dynamic graph streams
• New bounds for the CLIQUE-GAP problem using graph decomposition theory

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)