Parallel Dynamic Maximal Matching
<|reference_start|>Parallel Dynamic Maximal Matching: We present the first (randomized) parallel dynamic algorithm for maximal matching, which can process an arbitrary number of updates simultaneously. Given a batch of edge deletion or insertion updates to the graph, our parallel algorithm adjusts the maximal matching to these updates in $poly(\log n)$ depth and using $poly(\log n)$ amortized work per update. That is, the amortized work for processing a batch of $k$ updates is $kpoly(\log n)$, while all this work is done in $poly(\log n)$ depth, with high probability. This can be seen as a parallel counterpart of the sequential dynamic algorithms for constant-approximate and maximal matching [Onak and Rubinfeld STOC'10; Baswana, Gupta, and Sen FOCS'11; and Solomon FOCS'16]. Our algorithm readily generalizes to maximal matching in hypergraphs of rank $r$ -- where each hyperedge has at most $r$ endpoints -- with a $poly(r)$ increase in work, while retaining the $poly(\log n)$ depth.<|reference_end|>
@article{ghaffari2024parallel,
    title={Parallel Dynamic Maximal Matching},
    author={Mohsen Ghaffari, Anton Trygub},
    journal={arXiv preprint arXiv:2409.15476},
    year={2024},
    archivePrefix={arXiv},
    eprint={2409.15476},
    primaryClass={cs.DS cs.DC}
}