From Unweighted to Weighted Dynamic Matching in Non-Bipartite Graphs: A Low-Loss Reduction

We study the approximate maximum weight matching (MWM) problem in a fully dynamic graph subject to edge insertions and deletions. We design meta-algorithms that reduce the problem to the unweighted approximate maximum cardinality matching (MCM) problem. Despite recent progress on bipartite graphs – Bernstein-Dudeja-Langley (STOC 2021) and Bernstein-Chen-Dudeja-Langley-Sidford-Tu (SODA 2025) – the only previous meta-algorithm that applied to non-bipartite graphs suffered a \(\frac12\) approximation loss (Stubbs-Williams, ITCS 2017). We significantly close the weighted-and-unweighted gap by showing the first low-loss reduction that transforms any fully dynamic \((1-\varepsilon)\)-approximate MCM algorithm on bipartite graphs into afully dynamic \((1-\varepsilon)\)–approximate MWM algorithm on general (not necessarily bipartite) graphs, with only a \(\operatorname{poly}(\log n/\varepsilon)\) overhead in the update time. Central to our approach is a new primal–dual framework that reduces the computation of an approximate MWM in general graphs to a sequence of approximate induced matching queries on an auxiliary bipartite extension. In addition, we give the first conditional lower bound on approximate partially dynamic matching with worst-case update time.