New Approximation Algorithms for Dynamic Matching and Vertex Cover

We consider the problem of maintaining a matching and a vertex cover of approximately maximum (resp. minimum) size in a dynamic graph under a sequence of edge insertions and deletions. In recent years, a significant body of work has been devoted to this problem. Using a primal-dual framework, we first show how to maintain a (2+\epsilon) approximate maximum fractional matching and minimum vertex cover in O(log n/\epsilon^2) amortized update time, where n is the number of nodes in the input graph. Next, we show how to perform ``deterministic rounding'' efficiently in a dynamic setting, thereby converting the fractional matching maintained by the previous algorithm into an integral matching. Finally, we show how to make the update time of our fractional matching algorithm worst case, thereby getting the first non-trivial dynamic algorithm that is deterministic and has O(poly log n) worst case update time. We conclude by pointing out some interesting open problems in this area (joint work with M. Henzinger and G. Italiano (SODA 2015) and M. Henzinger and D. Nanongkai (STOC 2016, SODA 2017)).