Entropy Regularization and Faster Decremental Matching in General Graphs

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) • 2 O(1/ε 2 ) update time [Assadi-Bernstein-Dudeja 2022] and an O( √ mε -2 ) update time [Gupta-Peng 2013], and our weighted result improves upon the O( √ mε -O(1/ε) log n) update time due to [Gupta-Peng 2013].

To obtain our results, we generalize a recent optimization approach to dynamic algorithms from [Jambulapati-Jin-Sidford-Tian 2022]. We show that repeatedly solving entropy-regularized optimization problems yields a lazy updating scheme for fractional decremental problems with a near-optimal number of updates. To apply this framework we develop optimization methods compatible with it and new dynamic rounding algorithms for the matching polytope.

1 Independently and concurrently, Aditi Dudeja obtained new decremental weighted matching results for general graphs [Dud24a].