Some Recent Advances in Dynamic Algorithms for Maximum Matching and Minimum Set Cover (Part 1)

Speaker : Sayan Bhattacharya (University of Warwick)

Details:
Consider a dynamic graph G = (V, E) that is undergoing a sequence of edge insertions/deletions. We want to design an algorithm that maintains an (approximately) maximum matching in this dynamic graph G with small update time. Here, the update time of an algorithm refers to the time it takes to handle the insertion/deletion of an edge in G. We will like to ensure that the update time of our algorithm is polylogarithmic in the number of nodes G.

This problem has received considerable attention in the past decade. In these two talks, I will present an overview of some recent advances on this question. Specifically, I will describe a simple primal-dual algorithm that maintains a (2+\epsilon)-approximate "fractional" matching in G in polylogarithmic update time (Part 1), and show how to efficiently "round" this fractional matching into an integral one in the dynamic setting (Part 2).

Along the way, I will explain some immediate connections between dynamic fractional matching algorithms and the literature on dynamic set cover.