{"ID":2852442,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.19049","arxiv_id":"2510.19049","title":"From Unweighted to Weighted Dynamic Matching in Non-Bipartite Graphs: A Low-Loss Reduction","abstract":"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 $\\frac{1}{2}$ 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 a fully dynamic $(1-\\varepsilon)$-approximate MWM algorithm on general (not necessarily bipartite) graphs, with only a $\\mathrm{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.","short_abstract":"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-La...","url_abs":"https://arxiv.org/abs/2510.19049","url_pdf":"https://arxiv.org/pdf/2510.19049v1","authors":"[\"Aaron Bernstein\",\"Jiale Chen\"]","published":"2025-10-21T20:07:47Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}