From Unweighted to Weighted Dynamic Matching in Non-Bipartite Graphs: A Low-Loss Reduction
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911225959415808 |
|---|---|
| author | Bernstein, Aaron Chen, Jiale |
| author_facet | Bernstein, Aaron Chen, Jiale |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_19049 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | From Unweighted to Weighted Dynamic Matching in Non-Bipartite Graphs: A Low-Loss Reduction Bernstein, Aaron Chen, Jiale Data Structures and Algorithms 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. |
| title | From Unweighted to Weighted Dynamic Matching in Non-Bipartite Graphs: A Low-Loss Reduction |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2510.19049 |