An Asymptotically Optimal Algorithm for Maximum Matching in Dynamic Streams
Authors:
Sepehr Assadi, Vihan Shah.
Abstract:
We present an algorithm for the maximum matching problem in dynamic (insertion-deletions) streams
with asymptotically optimal space complexity: for any n-vertex graph, our algorithm with high
probability outputs an α-approximate matching in a single pass using O(n^2/α^3) bits of space.
A long line of work on the dynamic streaming matching problem has reduced the gap between
space upper and lower bounds first to n^o(1) factors [Assadi-Khanna-Li-Yaroslavtsev; SODA 2016] and
subsequently to polylog(n) factors [Dark-Konrad; CCC 2020]. Our upper bound now matches the DarkKonrad lower bound up to O(1) factors, thus completing this research direction.
Our approach consists of two main steps: we first (provably) identify a family of graphs, similar
to the instances used in prior work to establish the lower bounds for this problem, as the only “hard”
instances to focus on. These graphs include an induced subgraph which is both sparse and contains a
large matching. We then design a dynamic streaming algorithm for this family of graphs which is more
efficient than prior work. The key to this efficiency is a novel sketching method, which bypasses the
typical loss of polylog (n)-factors in space compared to standard L0-sampling primitives, and can be of
independent interest in designing optimal algorithms for other streaming problems.
Conference version:
[PDF]