The Complexity of Counting Cycles in the Adjacency List Streaming Model

We study the problem of counting cycles in the adjacency list streaming model, fully resolving in which settings there exist sublinear space algorithms. Our main upper bound is a two-pass algorithm for estimating triangles that uses $\wtO (m/T^2/3 )$ space, where m is the edge count and T is the triangle count of the graph. On the other hand, we show that no sublinear space multipass algorithm exists for counting $\ell$-cycles for $\ell \geq 5$. Finally, we show that counting 4-cycles is intermediate: sublinear space algorithms exist in multipass but not single-pass settings.

• Publication year

  2019

• Venue

  ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems

• Publication date

  2019-06-25

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1145/3294052.3319706
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Towards Tighter Space Bounds for Counting Triangles and Other Substructures in Graph Streams

  2017influential reference
• Better Algorithms for Counting Triangles in Data Streams

  2016influential reference
• Furthermore

  2016cited by this paper
• A Hybrid Sampling Scheme for Triangle Counting

  2016influential reference
• Dependent Random Graphs and Multiparty Pointer Jumping

  2015cited by this paper
• Triangle Counting in Dynamic Graph Streams

  2014cited by this paper
• Triangle counting in streamed graphs via small vertex covers

  2014cited by this paper
• Communication Lower Bounds Using Directional Derivatives

  2014cited by this paper
• A second look at counting triangles in graph streams

  2014cited by this paper
• Counting and Sampling Triangles from a Graph Stream

  2013cited by this paper
• PATRIC: a parallel algorithm for counting triangles in massive networks

  2013cited by this paper
• How Hard Is Counting Triangles in the Streaming Model?

  2013cited by this paper
• Counting Arbitrary Subgraphs in Data Streams

  2012cited by this paper
• The multiparty communication complexity of set disjointness

  2012cited by this paper
• A Space-Efficient Streaming Algorithm for Estimating Transitivity and Triangle Counts Using the Birthday Paradox

  2012cited by this paper
• Triangle Sparsifiers

  2011cited by this paper
• Colorful triangle counting and a MapReduce implementation

  2011cited by this paper
• Counting triangles and the curse of the last reducer

  2011cited by this paper
• Approximate Counting of Cycles in Streams

  2011cited by this paper
• Efficient Triangle Counting in Large Graphs via Degree-Based Vertex Partitioning

  2010cited by this paper
• Parallel external memory graph algorithms

  2010cited by this paper
• Sublinear Communication Protocols for Multi-Party Pointer Jumping and a Related Lower Bound

  2008cited by this paper
• Efficient semi-streaming algorithms for local triangle counting in massive graphs

  2008cited by this paper
• Tolerating the community detection resolution limit with edge weighting.

  2008cited by this paper
• Microscopic evolution of social networks

  2008cited by this paper
• Software and Algorithms for Graph Queries on Multithreaded Architectures

  2007cited by this paper
• A Brief Look at Pairings Based Cryptography

  2007cited by this paper
• Counting triangles in data streams

  2006cited by this paper
• New Streaming Algorithms for Counting Triangles in Graphs

  2005cited by this paper
• Reductions in streaming algorithms, with an application to counting triangles in graphs

  2002cited by this paper
• Curvature of co-links uncovers hidden thematic layers in the World Wide Web

  2001cited by this paper
• Proceedings of the twenty-seventh annual ACM symposium on Theory of computing

  1995cited by this paper
• On Randomized One-round Communication Complexity

  1995cited by this paper
• The Probabilistic Communication Complexity of Set Intersection

  1992cited by this paper
• On the Distributional Complexity of Disjointness

  1990cited by this paper
• Cycles of even length in graphs

  1974cited by this paper

• Streaming triangle counting: the impact of a degree oracle

  2026cites this paper
• Testable algorithms for approximately counting edges and triangles in sublinear time and space

  2025cites this paper
• Subgraph Counting under Edge Local Differential Privacy Based on Noisy Adjacency Matrix

  2025cites this paper
• Deterministic Lifting Theorems for One-Way Number-on-Forehead Communication

  2025cites this paper
• An Improved Fully Dynamic Algorithm for Counting 4-Cycles in General Graphs Using Fast Matrix Multiplication

  2025cites this paper
• Accurate and Fast Approximate Graph Pattern Mining at Scale

  2024cites this paper
• Near Uniform Triangle Sampling Over Adjacency List Graph Streams

  2024cites this paper
• Structured encryption for triangle counting on graph data

  2023cites this paper
• Hierarchical data structures for flowchart

  2023cites this paper
• Streaming Kernel PCA Algorithm With Small Space

  2023cites this paper
• Approximately Counting Subgraphs in Data Streams

  2022cites this paper
• Triangle and Four Cycle Counting with Predictions in Graph Streams

  2022cites this paper
• Differentially Private Subgraph Counting in the Shuffle Model

  2022cites this paper
• Differentially Private Triangle and 4-Cycle Counting in the Shuffle Model

  2022cites this paper
• Towards Multi-Pass Streaming Lower Bounds for Optimal Approximation of Max-Cut

  2022cites this paper
• Maximum Coverage in the Data Stream Model: Parameterized and Generalized

  2021cites this paper
• Counting Simplices in Hypergraph Streams

  2021cites this paper
• Edge sampling and graph parameter estimation via vertex neighborhood accesses

  2021influential citation
• Communication-Efficient Triangle Counting under Local Differential Privacy

  2021cites this paper
• An Optimal Algorithm for Triangle Counting

  2021cites this paper
• Graph streaming lower bounds for parameter estimation and property testing via a streaming XOR lemma

  2021cites this paper
• Small Circuits Imply Efficient Arthur-Merlin Protocols

  2021cites this paper
• Even the Easiest(?) Graph Coloring Problem is not Easy in Streaming!

  2020cites this paper
• Triangle and Four Cycle Counting in the Data Stream Model

  2020cites this paper
• On the Theoretical Properties of the Network Jackknife

  2020cites this paper
• Streaming Verification for Graph Problems: Optimal Tradeoffs and Nonlinear Sketches

  2020cites this paper
• Multi-Pass Graph Streaming Lower Bounds for Cycle Counting, MAX-CUT, Matching Size, and Other Problems

  2020cites this paper
• Graph Spanners by Sketching in Dynamic Streams and the Simultaneous Communication Model

  2020cites this paper
• Improved 3-pass Algorithm for Counting 4-cycles in Arbitrary Order Streaming

  2020cites this paper
• Streaming Verification of Graph Computations via Graph Structure

  2019cites this paper
• Subsampling Sparse Graphons Under Minimal Assumptions

  2019cites this paper
• Subsampling Sparse Graphons Under Minimal Assumptions

  year unknowncites this paper