A Fully-Dynamic Approximation Algorithm for Maximum Weight b-Matchings in Graphs
摘要
Matching nodes in a graph \(G=(V,E)\) is a well-studied algorithmic problem with many applications. The b-matching problem is a generalization that allows to match a node with up to b neighbors. This allows more flexible connectivity patterns whenever vertices may have multiple associations. The algorithm b-suitor [Khan et al., SISC 2016] is able to compute a (1/2)-approximation of a maximum weight b-matching in \(\mathcal {O}(|E|)\) time. Since real-world graphs often change over time, fast dynamic methods for b-matching optimization are desirable. In this work, we propose Dyn-b-suitor, a dynamic algorithm for the weighted b-matching problem. As a non-trivial extension to the dynamic Suitor algorithm for 1-matchings [Angriman et al., JEA 2022], our approach computes (1/2)-approximate b-matchings by identifying and updating affected vertices without static recomputation. Our proposed algorithm is fully-dynamic, i. e., it supports both edge insertions and deletions, and we prove that it computes the same solution as its static counterpart. In extensive experiments on real-world benchmark graphs and generated instances, our dynamic algorithm yields significant savings compared to the sequential b-suitor, e. g., for batch updates with \(10^3\) edges with an average acceleration factor of \(10^3\times \) . When comparing our sequential dynamic algorithm with the parallel (static) b-suitor on a 128-core machine, our dynamic algorithm is still \(59\times \) to \(10^4\times \) faster.