Room 327

Fully dynamic maximum b-matching in constant update time

Divyarthi M.

IMSc

In recent years, there has been extensive work on maintaining (approximate) maximum matching in dynamic graphs. We consider a generalisation of this problem known as the maximum $b$-matching: Every node $v$ has a positive integral capacity $b_v$, and the goal is to maintain an (approximate) maximum-cardinality subset of edges that contains at most $b_v$ edges incident on every node $v$. The maximum matching problem is a special case of this problem where $b_v = 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( \log^3 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+\epsilon)$-approximate maximum $b$-matching in expected amortised $O(1/\epsilon^4)$ update time. Thus, for every constant $\epsilon \in (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 using a hierarchical partition of the node-set.

This is joint work with Sayan Bhattacharya and Manoj Gupta.