On Estimating Maximum Matching Size in Graph Streams

Abstract

We study the problem of estimating the maximum matching size in graphs whose edges are revealed in a streaming manner. We consider both insertion-only streams and dynamic streams and present new upper and lower bound results for both models. On the upper bound front, we show that an $\alpha$-approximate estimate of the matching size can be computed in dynamic streams using $\tilde{O}(n^2/{\alpha }^4)$ space, and in insertion-only streams using $\tilde{O}(n/{\alpha }^2)$-space. On the lower bound front, we prove that any $\alpha$-approximation algorithm for estimating matching size in dynamic graph streams requires $\Omega (\sqrt{n}/{\alpha }^{2.5})$ bits of space, even if the underlying graph is both sparse and has arboricity bounded by $O(\alpha )$. We further improve our lower bound to $\Omega (n/{\alpha }^2)$ in the case of dense graphs. Furthermore, we prove that a $(1+\epsilon )$-approximation to matching size in insertion-only streams requires RS$(n)\cdot n^{1-O(\epsilon )}$ space; here, RS$n$ denotes the maximum number of edge-disjoint induced matchings of size $\Theta (n)$ in an $n$-vertex graph. It is a major open problem to determine the value of RS$(n)$, and current results leave open the possibility that RS$(n)$ may be as large as $n/\log n$. We also show how to avoid the dependency on the parameter RS$(n)$ in proving lower bound for dynamic streams and present a near-optimal lower bound of $n^{2-O(\epsilon )}$ for $(1+\epsilon )$-approximation in this model. Using a well-known connection between matching size and matrix rank, all our lower bounds also hold for the problem of estimating matrix rank. In particular our results imply a near-optimal $n^{2-O(\epsilon )}$ bit lower bound for $(1+\epsilon )$-approximation of matrix ranks for dense matrices in dynamic streams, answering an open question of Li and Woodruff (STOC 2016).

Cited by in corpus (21)

• Maximum matchings and minimum dominating sets in Apollonian networks and extended Tower of Hanoi graphs
• Maximum Matching in Two, Three, and a Few More Passes Over Graph Streams
• A $(2+\epsilon )$-Approximation for Maximum Weight Matching in the Semi-Streaming Model
• Massively Parallel Symmetry Breaking on Sparse Graphs: MIS and Maximal Matching
• Dynamic Streaming Spectral Sparsification in Nearly Linear Time and Space
• Testable Bounded Degree Graph Properties Are Random Order Streamable
• Vector-Matrix-Vector Queries for Solving Linear Algebra, Statistics, and Graph Problems
• Optimal lower bounds for universal relation, samplers, and finding duplicates
• Improved Bound for Matching in Random-Order Streams
• Randomized Composable Coresets for Matching and Vertex Cover
• Independent Set Size Approximation in Graph Streams
• Graph Streaming Lower Bounds for Parameter Estimation and Property Testing via a Streaming XOR Lemma
• Multi-Pass Graph Streaming Lower Bounds for Cycle Counting, MAX-CUT, Matching Size, and Other Problems
• Distributed Weighted Matching via Randomized Composable Coresets
• Near-Quadratic Lower Bounds for Two-Pass Graph Streaming Algorithms
• Optimal Streaming Algorithms for Graph Matching
• A Two-Pass Lower Bound for Semi-Streaming Maximum Matching
• Optimality of Linear Sketching under Modular Updates
• Two Player Hidden Pointer Chasing and Multi-Pass Lower Bounds in Turnstile Streams
• How the Degeneracy Helps for Triangle Counting in Graph Streams
• Noisy Boolean Hidden Matching with Applications