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.
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.
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