Campus Event Calendar

Event Entry

What and Who

Dynamic Matching with Better-than-2 Approximation in Polylogarithmic Update Time

Peter Kiss
Max-Planck-Institut für Informatik - D1
AG1 Mittagsseminar (own work)
AG 1  
AG Audience

Date, Time and Location

Thursday, 1 December 2022
30 Minutes
E1 4


We present dynamic algorithms with polylogarithmic update time for estimating the size of the maximum matching of a graph undergoing edge insertions and deletions with approximation ratio strictly better than 2. Specifically, we obtain a 1+(1/\sqrt{2})+ϵ≈1.707+ϵ approximation in bipartite graphs and a 1.973+ϵ approximation in general graphs. We thus answer in the affirmative the major open question first posed in the influential work of Onak and Rubinfeld (STOC'10) and repeatedly asked in the dynamic graph algorithms literature. Our randomized algorithms also work against an adaptive adversary and guarantee worst-case polylog update time, both w.h.p.

Our algorithms are based on simulating new two-pass streaming matching algorithms in the dynamic setting. Our key new idea is to invoke the recent sublinear-time matching algorithm of Behnezhad (FOCS'21) in a white-box manner to efficiently simulate the second pass of our streaming algorithms, while bypassing the well-known vertex-update barrier.


Roohani Sharma
+49 681 9325 1116
--email hidden

Virtual Meeting Details

passcode not visible
logged in users only

Tags, Category, Keywords and additional notes

If you wish to attend the talk online, but do not have the password, contact Roohani Sharma at

Roohani Sharma, 11/29/2022 23:47
Roohani Sharma, 11/18/2022 16:31
Roohani Sharma, 11/18/2022 15:15 -- Created document.