Parallel Batch-Dynamic Maximal Matching with Constant Work per Update

We present a work optimal algorithm for parallel fully batch-dynamic maximal matching against an oblivious adversary. It processes batches of updates (either insertions or deletions of edges) in constant expected amortized work per edge update, and in O (log3 m) depth per batch whp, where m is the maximum number of edges in the graph over time. This greatly improves on the recent result by Ghaffari and Trygub (2024) that requires O (log9 m) amortized work per update and O (log4 m) depth per batch, both whp.