Tata Institute of Fundamental Research

New Approximation Algorithms for Dynamic Matching and Vertex Cover

STCS Seminar
Speaker: Sayan Bhattacharya (Institute of Mathematical Sciences IV Cross Road CIT Campus Taramani Chennai 600113)
Organiser: Jaikumar Radhakrishnan
Date: Tuesday, 31 Jan 2017, 16:00 to 17:00
Venue: A-201 (STCS Seminar Room)

(Scan to add to calendar)
Abstract:  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(\mathrm{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)).