Fully Dynamic Approximate Matching

EADS talk by Aaron Bernstein


We study the problem of maintaining an approximate maximum cardinality matching in an unweighted graph G that is subject to a sequence of insertions and deletions. The goal is recompute the approximate matching as quickly as possible after each insertion/deletion. Currently, there exist randomized algorithms with only polylog update time for maintaining a 2-or-worse approximate matching (e.g. a maximal matching), while the fastest update time for any algorithm that achieves a better-than-2 approximation is O(m^(1/2)). Intuitively the reason for this large gap is that maintaining a maximal (2-approximate) matching is a purely local problem in that as long as we match all legal edges, it does not matter which edges we choose: if both (u,v) and (u,w) are legal, either one can be chosen for the 2-approximate matching. To go beyond a 2-approximation, we need to keep track of some global structure in the graph, which is difficult to do in a dynamic setting. 

In our paper, we set out to devise faster algorithms for maintaining a better-than-2 approximations. Our main result achieves an update time of m^(1/4) for a (3/2 + eps) approximation; the state of the art needs m^{1/2} update time, though it achieves a (1 + epsilon) approximation. Our algorithm achieves the fastest update time for a better-than-2 approximation, as well as the fastest existing deterministic update time for any constant approximation. Our approach also leads to some new results for small arboricity graphs.  Our main technique is (loosely speaking) a new way of characterizing (1+eps) and (3/2+eps) approximate matchings -- one that does not rely on the non-existence of short augmenting paths. 


This talk is based on two papers (ICALP 2015, SODA 2016), both joint work with Cliff Stein.