Space Lower Bounds for Approximating Maximum Matching in the Edge Arrival Model

Michael Kapralov

Introduction

In the analysis of large-scale graphs, the "semi-streaming" model is a standard framework where an algorithm processes edges one by one and is restricted to $O(n \cdot \text{poly} \log n)$ space. For the Maximum Bipartite Matching problem, a simple greedy approach yields a $1/2$-approximation. While the "vertex-arrival" model—where all edges incident to a vertex arrive together—allows for a $1-1/e \approx 0.632$ approximation, the more general "edge-arrival" model, where edges arrive in an arbitrary order, has long lacked a tight upper bound. This paper by Michael Kapralov establishes that edge-arrival streams are fundamentally harder, proving a space lower bound for any approximation better than $1/(1+\ln 2) \approx 0.59$.

Gadget Chaining and Hard Distributions

The core of the proof lies in constructing a "hard instance" that forces any space-constrained algorithm to lose information. The construction utilizes a sequence of $L$ chained "KVV gadgets" (named after Karp, Vazirani, and Vazirani). These gadgets are bipartite graphs designed such that the maximum matching is hidden behind a random permutation.

The construction chains multiple KVV gadgets to force irrevocable decisions under space constraints.

By stringing these gadgets together, the author ensures that an algorithm must make a series of decisions without knowing which vertices will be most valuable in future parts of the stream. This "chaining" effectively amplifies the uncertainty, leading to the derived hardness threshold.

Glueing and Densifying Maps

To maintain the hardness property across the entire chain in a streaming setting, the paper introduces a sophisticated technical framework involving "glueing maps" ($\tau$) and "densifying maps" ($\rho$). These maps mathematically link the "output" vertices of one gadget to the "input" vertices of the next.

Glueing maps ($\tau$) link vertex sets across different layers ($P$ and $Q$) of the chained construction.

The construction leverages techniques from Ruzsa-Szemerédi graphs—graphs that are locally sparse but globally dense. This makes it impossible for an algorithm to store enough edge information to identify the optimal matching across the chain without exceeding the semi-streaming space limit of $O(n \cdot \text{poly} \log n)$.

Key Results

The primary result is a formal separation between the space complexity of vertex-arrival and edge-arrival models:

  • Theorem 1: Any single-pass streaming algorithm that finds a $(\frac{1}{1+\ln 2} + \eta)$-approximate matching for any constant $\eta > 0$ must use $n^{1+\Omega(1/\log \log n)}$ bits of space.

The constant $1/(1+\ln 2) \approx 0.59$ represents the theoretical limit where the decay of matching information across the chained gadgets becomes insurmountable for sub-linear space algorithms.

Conclusion and Future Work

This work provides the first significant separation between arrival models in the semi-streaming setting. While it lowers the upper bound to 0.59, a gap remains between this result and the 0.5 greedy lower bound. Future research may focus on closing this gap or extending these geometric techniques to multi-pass algorithms, where the space-approximation trade-offs are still poorly understood.

Summary updated

BibTeX
@inproceedings{kapralov2021space,
  author = {Michael Kapralov},
  title = {{Space Lower Bounds for Approximating Maximum Matching in the Edge Arrival Model}},
  booktitle = {SODA},
  year = {2021},
  doi = {10.1137/1.9781611976465.112},
}
Figure