Decremental Matching in General Graphs
Authors:
Sepehr Assadi, Aaron Bernstein, Aditi Dudeja.
Abstract:
We consider the problem of maintaining an approximate maximum integral matching in a dynamic
graph G, while the adversary makes changes to the edges of the graph. The goal is to maintain a
(1 + ε)-approximate maximum matching for constant ε > 0, while minimizing the update time. In
the fully dynamic setting, where both edge insertion and deletions are allowed, Gupta and Peng (see
[GP13]) gave an algorithm for this problem with an update time of O(√m/ε^2).
Motivated by the fact that the Oε(√m) barrier is hard to overcome (see Henzinger, Krinninger, Nanongkai, and Saranurak [HKNS15]; Kopelowitz, Pettie, and Porat [KPP16]), we study this problem in the decremental model, where the adversary is only allowed to delete edges. Recently, Bernstein, Probst-Gutenberg, and Saranurak (see [BGS20]) gave an poly(log n/ε) update time decremental algorithm for this problem in bipartite graphs. However, beating O(√m) update time remained an open problem for general graphs.
In this paper, we bridge the gap between bipartite and general graphs, by giving an Oε(poly(log n)) update time algorithm that maintains a (1 + ε)-approximate maximum integral matching under adversarial deletions. Our algorithm is randomized, but works against an adaptive adversary. Together with the work of Grandoni, Leonardi, Sankowski, Schwiegelshohn, and Solomon [GLS+19] who give an Oε(1) update time algorithm for general graphs in the incremental (insertion-only) model, our result essentially completes the picture for partially dynamic matching.
Motivated by the fact that the Oε(√m) barrier is hard to overcome (see Henzinger, Krinninger, Nanongkai, and Saranurak [HKNS15]; Kopelowitz, Pettie, and Porat [KPP16]), we study this problem in the decremental model, where the adversary is only allowed to delete edges. Recently, Bernstein, Probst-Gutenberg, and Saranurak (see [BGS20]) gave an poly(log n/ε) update time decremental algorithm for this problem in bipartite graphs. However, beating O(√m) update time remained an open problem for general graphs.
In this paper, we bridge the gap between bipartite and general graphs, by giving an Oε(poly(log n)) update time algorithm that maintains a (1 + ε)-approximate maximum integral matching under adversarial deletions. Our algorithm is randomized, but works against an adaptive adversary. Together with the work of Grandoni, Leonardi, Sankowski, Schwiegelshohn, and Solomon [GLS+19] who give an Oε(1) update time algorithm for general graphs in the incremental (insertion-only) model, our result essentially completes the picture for partially dynamic matching.
Conference version:
[PDF]
Full version:
[arXiv]
BibTex:
[DBLP]