# Settling the Pass Complexity of Approximate Matchings in Dynamic Graph Streams

#### Abstract

A semi-streaming algorithm in **dynamic graph streams** processes any $n$-vertex graph by making one or multiple passes over a stream of insertions and deletions to edges of the graph and
using $O(n \cdot \text{polylog} ~ {n})$ space. Semi-streaming algorithms for dynamic streams were first obtained
in the seminal work of Ahn, Guha, and McGregor in 2012, alongside the introduction of the *graph sketching* technique,
which remains the de facto way of designing algorithms in this model and a highly popular technique for designing graph algorithms in general.

We settle the pass complexity of approximating **maximum matchings** in dynamic streams via semi-streaming algorithms by improving the state-of-the-art in *both* upper and lower bounds:

- We present a randomized sketching based semi-streaming algorithm for $O(1)$-approximation of maximum matching in dynamic streams using $O(\log\log{n})$ passes. The approximation ratio of this algorithm can be improved to $(1+\varepsilon)$ for any fixed $\varepsilon > 0$ even on weighted graphs using standard techniques. This exponentially improves upon several $O(\log{n})$ pass algorithms developed for this problem since the introduction of the dynamic graph streaming model.
- We prove that any semi-streaming algorithm (not only sketching based) for $O(1)$-approximation of maximum matching in dynamic streams requires $\Omega(\log\log{n})$ passes. This presents the first multi-pass lower bound for this problem, which is already also optimal, settling a longstanding open question in this area.

**Preprint**| arXiv

2024 © Kheeran K. Naidu