Decremental Matching in General Graphs
share
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 <cit.>) 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 [BPT20]) gave an O_ϵ(1) 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_ϵ(1) 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 [GLSSS19] 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.
READ FULL TEXT