Dynamic Primal Dual Algorithms for Vertex Cover and Matching

Consider a scenario where we are given an input graph G = (V, E), and at each time-step either a new edge is inserted into the graph or an already existing edge is deleted from the graph. In this dynamic setting, we want to maintain an approximately minimum vertex cover and an approximately maximum matching in G.

Our main result is a deterministic primal-dual algorithm for this problem. The algorithm maintains a (2+\epsilon)-approximate minimum vertex cover in O(\log n/\epsilon^2) amortized update time, where n denotes the number of nodes. This answers an open question from Onak and Rubinfield [STOC' 2010]. We can also maintain a (3+\epsilon)-approximate maximum matching in O(m^{1/3}) amortized update time, where m denotes the number of edges in the graph.

We also describe extensions of our framework to dynamic set cover and dynamic b-matching problems (joint work with Monika Henzinger and Guiseppe Italiano, based on work that appeared in SODA 2015 and ICALP 2015).