Matching Composition and Efficient Weight Reduction in Dynamic Matching

We consider the foundational problem of maintaining a (1-ε)-approximate maximum weight matching (MWM) in an n-node dynamic graph undergoing edge insertions and deletions. We provide a general reduction that reduces the problem on graphs with a weight range of poly(n) to poly(1/ε) at the cost of just an additive poly(1/ε) in update time. This improves upon the prior reduction of Gupta-Peng (FOCS 2013) which reduces the problem to a weight range of ε -O(1/ε) with a multiplicative cost of O(log n).

When combined with a reduction of Bernstein-Dudeja-Langley (STOC 2021) this yields a reduction from dynamic (1 -ε)-approximate MWM in bipartite graphs with a weight range of poly(n) to dynamic (1 -ε)-approximate maximum cardinality matching in bipartite graphs at the cost of a multiplicative poly(1/ε) in update time, thereby resolving an open problem in [GP'13; BDL'21]. Additionally, we show that our approach is amenable to MWM problems in streaming, shared-memory work-depth, and massively parallel computation models. We also apply our techniques to obtain an efficient dynamic algorithm for rounding weighted fractional matchings in general graphs. Underlying our framework is a new structural result about MWM that we call the "matching composition lemma" and new dynamic matching subroutines that may be of independent interest.