2024/10/24 by Aaron Bernstein, Bernstein, Aaron, Jiale Chen +9 · 1 citation
Medicine · Biochemistry, Genetics and Molecular Biology · #Nutritional Studies and Diet #Metabolomics and Mass Spectrometry Studies
paper · pdf · doi:10.48550/arxiv.2410.18936
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.