# Beating the Folklore Algorithm for Dynamic Matching

arXiv: https://arxiv.org/abs/2106.10321 · HTML: https://mlsanity.com/paper/2106.10321/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Jun 2021.

## Built on by (most cited first, 1 of 1)

- [Fast White-Box Adversarial Streaming Without a Random Oracle](https://mlsanity.com/paper/2406.06808/) (2024)

## Abstract (arXiv)

The maximum matching problem in dynamic graphs subject to edge updates (insertions and deletions) has received much attention over the last few years; a multitude of approximation/time tradeoffs were obtained, improving upon the folklore algorithm, which maintains a maximal (and hence 2-approximate) matching in O(n) worst-case update time in n-node graphs. We present the first deterministic algorithm which outperforms the folklore algorithm in terms of em both approximation ratio and worst-case update time. Specifically, we give a (2-Omega(1))-approximate algorithm with O(m3/8)=O(n3/4) worst-case update time in n-node, m-edge graphs. For sufficiently small constant ε>0, no deterministic (2+ε)-approximate algorithm with worst-case update time O(n0.99) was known. Our second result is the first deterministic (2+ε)-approximate weighted matching algorithm with Oε(1)· O(√[4]m) = Oε(1)· O(√n) worst-case update time. Our main technical contributions are threefold: first, we characterize the tight cases for kernels, which are the well-studied matching sparsifiers underlying much of the (2+ε)-approximate dynamic matching literature. This characterization, together with multiple ideas -- old and new -- underlies our result for breaking the approximation barrier of 2. Our second technical contribution is the first example of a dynamic matching algorithm whose running time is improved due to improving the recourse of other dynamic matching algorithms. Finally, we show how to use dynamic bipartite matching algorithms as black-box subroutines for dynamic matching in general graphs without incurring the natural frac32 factor in the approximation ratio which such approaches naturally incur.