Decremental Matching in General Graphs

07/03/2022
by   Sepehr Assadi, et al.
0

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

Please sign up or login with your details

Forgot password? Click here to reset

Sign in with Google

×

Use your Google Account to sign in to DeepAI

×

Consider DeepAI Pro