Beating Two-Thirds For Random-Order Streaming Matching

Abstract

We study the maximum matching problem in the random-order semi-streaming setting. In this problem, the edges of an arbitrary $n$-vertex graph $G=(V,E)$ arrive in a stream one by one and in a random order. The goal is to have a single pass over the stream, use $n\cdot poly(\log n)$ space, and output a large matching of $G$. We prove that for an absolute constant ${\epsilon }_0>0$, one can find a $(2/3+{\epsilon }_0)$-approximate maximum matching of $G$ using $O(n\log n)$ space with high probability. This breaks the natural boundary of $2/3$ for this problem prevalent in the prior work and resolves an open problem of Bernstein [ICALP'20] on whether a $(2/3+\Omega (1))$-approximation is achievable.