A framework for dynamic matching in weighted graphs

We introduce a new framework for computing approximate maximum weight matchings. Our primary focus is on the fully dynamic setting, where there is a large gap between the guarantees of the best known algorithms for computing weighted and unweighted matchings. In particular, almost all existing weighted matching algorithms are obtained via a reduction to the unweighted problem that loses a factor of two in the approximation ratio. In contrast, in other sublinear models, such as the distributed and streaming models, recent work has largely closed this weighted/unweighted gap.

For bipartite graphs, we almost completely settle this gap with a general reduction that converts any algorithm for α-approximate unweighted matching to an algorithm for (1 -ε)αapproximate weighted matching, while only increasing the update time by a log n factor. We also show that our framework leads to significant improvements for non-bipartite graphs, though not in the form of a universal reduction. In particular, we show two algorithms for weighted non-bipartite matching:

• A randomized (Las Vegas) fully dynamic algorithm that maintains a ( 1 /2 -ε)-approximate maximum weight matching in worst-case update time O ε (polylog(n)) with high probability against an adaptive adversary. Our bounds are essentially the same as those of the unweighted algorithm of Wajc [STOC 2020].

• A deterministic fully dynamic algorithm that maintains a ( 2 /3 -ε)-approximate maximum weight matching in amortized update time Õε (m 1 /4 ). Our bounds are essentially the same as those of the unweighted algorithm of Bernstein and Stein [SODA 2016].

A key feature of our framework is that it uses existing algorithms for unweighted matching as black-boxes without modification. As a result, our framework is simple and versatile. Moreover, our framework easily translates to other models, and we use it to derive new results for the weighted matching problem in streaming and communication complexity models.