Entropy Regularization and Faster Decremental Matching in General Graphs
Jiale Chen, Aaron Sidford, Ta-Wei Tu · Society for Industrial and Applied Mathematics eBooks · 2025
We provide an algorithm that maintains, against an adaptive adversary, a (1 — ε )-approximate maximum matching in n-node m-edge general (not necessarily bipartite) undirected graph undergoing edge deletions with high probability with (amortized) O (poly(ε-1, log n )) time per update. We also obtain the same update time for maintaining a fractional approximate weighted matching (and hence an approximation to the value of the maximum weight matching) and an integral approximate weighted matching in dense graphs.1 Our unweighted result improves upon the prior state-of-the-art which includes a poly(log n ) · 2O (1/ɛ2) update time [Assadi-Bernstein-Dudeja 2022] and an update time [Gupta-Peng 2013], and our weighted result improves upon the log n ) update time due to [Gupta-Peng 2013].