A Faster Deterministic Algorithm for Fully Dynamic Maximal Matching To appear in STOC 2026.
Julia Chuzhoy, Sanjeev Khanna, Junkai Song · 2026
Read A Faster Deterministic Algorithm for Fully Dynamic Maximal Matching To appear in STOC 2026. by Julia Chuzhoy, Sanjeev Khanna, Junkai Song (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-00797.txt.
Introduction
Julia Chuzhoy, Sanjeev Khanna, and Junkai Song improve the deterministic algorithm for maintaining a maximal matching in a graph whose edges arrive and depart online. A maximal matching leaves no two unmatched vertices joined by an edge. Randomized methods are fast when the adversary is oblivious, but an adaptive adversary, who reacts to earlier choices, has been a major challenge.
A recent breakthrough gave the first sublinear update times against adaptive adversaries, with a deterministic bound slower than the randomized one. The new deterministic algorithm reaches an amortized update time near the square root of the number of vertices. Matching sparsifiers, sparse subgraphs that preserve key matching information, play a central tool role in the advance.
Catalog record
| CREATOR | Julia Chuzhoy, Sanjeev Khanna, Junkai Song |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 215 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.00797