Semi-streaming Matching in a Single Pass: A New Framework for Lower Bounds via Blueprints

In the semi-streaming model, we have an n-vertex graph G = (V, E) whose edges arrive in an arbitrary order in a stream. The goal is to make one or a few passes over the stream, use a limited memory of O(n) := O(n • polylog n) bits, and output a solution to the problem at hand at the end. A central open question in this area is to determine the best approximation ratio possible for the maximum matching problem via single-pass semi-streaming algorithms.

This problem admits a simple 0.5-approximation algorithm-by maintaining a maximal matching greedily-which, despite extensive efforts, has remained the state of the art. Lower bounds for this problem have also been few and far between with best known bounds ruling out better than 1/(1 + ln (2)) ∼ 0.590 approximation, using a highly complicated construction motivated by the literature on Ruzsa-Szemerédi (RS) graphs from extremal graph theory.

We develop a new framework for proving lower bounds for the semi-streaming matching problem. Our framework abstracts out the extremal graph theory and information theoretic arguments in the lower bounds, and reduces the problem to constructing certain constant-size graphs, which we call blueprints. Not only existing lower bounds can be captured by these blueprints-leading to far simpler and more concise arguments-but also we can design new blueprints that can be used to rule out (8 -2 √ 10)/3 ∼ 0.558-approximation for the semistreaming matching problem. We believe this approach can be of its own independent interest and lead to further improvements on this tantalizing open question.

Very recently, we built on this framework to rule out any single-pass semistreaming algorithm with approximation ratio strictly better than half. This shows that the simple greedy algorithm for the problem is already optimal, settling the central open question at the heart of this work. That paper appears on arXiv under the title: