A Two-Pass Lower Bound for Semi-Streaming Maximum Matching

Abstract

We prove a lower bound on the space complexity of two-pass semi-streaming algorithms that approximate the maximum matching problem. The lower bound is parameterized by the density of Ruzsa-Szemeredi graphs: * Any two-pass semi-streaming algorithm for maximum matching has approximation ratio at least $(1-\Omega (\frac{\log RS(n)}{\log n}))$, where $RS(n)$ denotes the maximum number of induced matchings of size $\Theta (n)$ in any $n$-vertex graph, i.e., the largest density of a Ruzsa-Szemeredi graph. Currently, it is known that $n^{\Omega (1/\log \log n)}\le RS(n)\le \frac{n}{2^{O({\log }^{\ast }(n))}}$ and closing this (large) gap between upper and lower bounds has remained a notoriously difficult problem in combinatorics. Under the plausible hypothesis that $RS(n)=n^{\Omega (1)}$, our lower bound is the first to rule out small-constant approximation two-pass semi-streaming algorithms for the maximum matching problem, making progress on a longstanding open question in the graph streaming literature.

arXiv comment40 pages, 10 figures

References in corpus (11)

• On Estimating Maximum Matching Size in Graph Streams
• Sublinear Estimation of Weighted Matchings in Dynamic Data Streams
• Streaming Algorithms for Submodular Function Maximization
• Maximum Matching in Two, Three, and a Few More Passes Over Graph Streams
• Space-Efficient Interior Point Method, with applications to Linear Programming and Maximum Weight Bipartite Matching
• On Two-Pass Streaming Algorithms for Maximum Bipartite Matching
• Nearly Complete Graphs Decomposable into Large Induced Matchings and their Applications
• Improved Bound for Matching in Random-Order Streams
• Space Lower Bounds for Approximating Maximum Matching in the Edge Arrival Model
• Graph Streaming Lower Bounds for Parameter Estimation and Property Testing via a Streaming XOR Lemma
• Optimal Lower Bounds for Matching and Vertex Cover in Dynamic Graph Streams

Cited by in corpus (1)

• On Two-Pass Streaming Algorithms for Maximum Bipartite Matching