Improved algorithm for dynamic b-matching

Abstract

Recently there has been extensive work on maintaining (approximate) maximum matchings in dynamic graphs. We consider a generalisation of this problem known as the maximum b-matching: Every node v has a positive integral capacity bv, and the goal is to maintain an approximate) maximum cardinality subset of edges that contains at most bv edges incident on every node v. The maximum matching problem is a special case of this problem where bv = 1 for every node v. Bhattacharya, Henzinger and Italiano [ICALP 2015] showed how to maintain a O(1) approximate maximum b-matching in a graph in O(log3 n) amortised update time. Their approximation ratio was a large (double digit) constant. We significantly improve their result both in terms of approximation ratio as well as update time. Specifically, we design a randomised dynamic algorithm that maintains a (2 + )-approximate maximum b-matching in expected amortised O(1= 4) update time. Thus, for every constant 2 (0; 1), we get expected amortised O(1) update time. Our algorithm generalises the framework of Baswana, Gupta, Sen [FOCS 2011] and Solomon [FOCS 2016] for maintaining a maximal matching in a dynamic graph.