Sayan Bhattacharya, University of Warwick

Abstract

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. 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 our algorithm has small (polylogarithmic) update time. 

This problem has received considerable attention in the past decade. In this talk, I will present an overview of some of my recent work on this topic. Specifically, I will describe a simple primal-dual algorithm that maintains a (2+epsilon)-approximate maximum {em fractional} matching in G in polylogarithmic update time, and show how to efficiently {em round} this fractional matching into an integral one in this dynamic setting.

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

Location: The Theory of Computing Seminar is being held online. Contact the organizers for the link to the seminar. 

See: https://sites.google.com/view/dimacs-theory-seminar/home