Source-linked AI summary
The Power of Local Marginals: An $O(\varepsilon^{-1})$-Aspect-Ratio Reduction for Dynamic Weighted Matching
Jiale Chen
TL;DR
Dynamic matching seeks fast maintenance of large or approximate matchings despite conditional lower bounds, while existing reductions have limitations in value compatibility and local aspect ratio. This paper develops a local-marginal reduction and obtains improved value and explicit-matching compositions, including a bipartite MWM consequence.
Problem
Dynamic matching seeks efficient maintenance after edge updates, but conditional lower bounds rule out O(n^(1−δ)) amortized update time for exact bipartite maximum cardinality matching, and existing reductions have value-compatibility limitations.
Method
The reduction groups edges into weight classes and uses local marginal contributions within weight windows, combining local MWM information to reduce polynomial aspect ratio to O(ε^−1).
Results
The reduction supports both value and explicit-matching composition, and applied to BKS23 yields a randomized fully dynamic bipartite MWM-value algorithm with m^(1/2−Ω_ε(1)) worst-case update time.
Takeaways & Limitations
The O(ε^−1) local aspect ratio is asymptotically tight for the stated value-only and matching composition frameworks, while the reduction transfers an MCM improvement to bipartite MWM value.
Takeaways & Limitations
The value lower bound applies only to reductions using local MWM values, while the matching lower bound assumes adversarial choices of local MWMs.
Abstract
from arXiv · showhide
We study dynamic maximum weight matching (MWM) under edge insertions and deletions in two settings: maintaining a $(1\pm\varepsilon)$-approximation to the optimum weight, and maintaining an explicit $(1-\varepsilon)$-approximate matching. Our main result is a reduction that transforms instances of polynomial aspect ratio into instances of aspect ratio $O(\varepsilon^{-1})$. The reduction applies to general graphs in both settings and is compatible with partially dynamic updates. The reduction is based on a structural property of local marginals. After grouping edges into weight classes, the global marginal contribution of one class relative to all lower classes is approximated by its marginal contribution within a local weight window of aspect ratio $O(\varepsilon^{-1})$. Summing these local marginals yields a value composition lemma that uses only approximate optimum values of the local windows. This improves the value reduction of Gupta and Peng (FOCS 2013), whose local aspect ratio is $\varepsilon^{-Θ(\varepsilon^{-1})}$. The same structural property yields an improved matching composition lemma for explicit matchings, reducing the local aspect ratio of Bernstein--Chen--Dudeja--Langley--Sidford--Tu (SODA 2025) from $O(\varepsilon^{-2})$ to $O(\varepsilon^{-1})$.
1 Introduction
Dynamic matching seeks fast maintenance of approximate values or explicit matchings despite strong barriers in fully dynamic settings. This paper answers the value-reduction question with local-marginal composition, reducing polynomial aspect ratio to O(ε^-1) windows and improving explicit-matching reductions.
- Motivation: Dynamic matching maintains a large matching after edge insertions and deletions, while exact matching faces conditional barriers against strongly sublinear update times.Approximation is therefore motivated in both value-only and explicit-matching settings.
- Prior gap: Value-only algorithms estimate matching weight or cardinality, whereas explicit-matching reductions must output an actual matching.Existing low-loss reductions requiring explicit matchings do not apply directly to value-only breakthroughs.
- Local marginals: The reduction partitions weights into dyadic classes and approximates each class’s global marginal contribution using a local weight window.Choosing h = ⌈log(ε^-1)⌉ + Θ(1) gives windows of aspect ratio O(ε^-1).
- Value composition: Local approximate optimum values compose into a global MWM-weight approximation, reducing polynomial aspect ratio to O(ε^-1) with low overhead and supporting general graphs.For bipartite graphs, graph unfolding converts MCM-value algorithms into MWM-value algorithms with eO(ε^-2) overhead.
- Matching composition: Local matchings from O(ε^-1)-aspect-ratio windows compose into a (1 − ε)-MWM, improving the prior local aspect ratio from eO(ε^-2) to O(ε^-1).The associated additive update overhead improves from eO(ε^-6) to eO(ε^-3).
- Limits: The O(ε^-1) local aspect ratio is asymptotically tight for value-only and matching composition under the paper’s stated information and adversarial-choice conditions.The value lower bound does not cover reductions using additional window information.
- Applications: Applications transfer a polynomial improvement from MCM cardinality to MWM weight and yield new low-arboricity and other dynamic explicit-MWM bounds.The low-arboricity sparsifier has O(αε^-1) degree and gives amortized update time eO(αε^-4).
2 Value and Matching Composition
The section develops a local exchange lemma showing that global matching interactions can be controlled within overlapping weight windows. This yields value and matching composition lemmas with O(ε^-1)-aspect-ratio windows, alongside tightness bounds for local information.
- Local exchange: Weight classes partition rescaled edges into Ei, while G[a,b] denotes the subgraph induced by consecutive classes and G≤i denotes a prefix.The local windows used throughout are G[i-h,i] and G[i-h,i-1].
- Local exchange: A local exchange repartitions a prefix matching and a window matching into matchings on G≤i and G[i-h,i-1], losing only a small amount of weight.The reverse repartitioning direction also holds, enabling comparisons between prefix and local-window optima.
- Local exchange: Each edge in Ei causes at most two deletions during the exchange, and the total deleted weight is at most 2^(1-h)µw(Gi).The bound follows because deleted edges have weight less than 2^-h times the triggering edge weight.
- Value composition: Summing local marginal contributions approximates the global MWM weight, with the accumulated error controlled by the total weight of local MWMs.The proof uses telescoping prefix differences and a bound obtained by processing windows by residue classes.
- Value composition: For 0 < ε ≤ 1/2, h = ⌈log(20/ε)⌉ and ρ = ε/[10(2h+1)] give a (1 ± ε)-approximation using windows of aspect ratio at most 80/ε.The value composition lemma uses approximate optimum values from the local windows.
- Matching composition: Explicit local matchings can be combined incrementally: adding Mi to an accumulated matching Pi−1 approximately realizes the global marginal contribution.Taking each Pi as an MWM on Pi−1 ∪ Mi and summing the resulting inequalities gives matching composition.
- Matching composition: For 0 < ε ≤ 1/2, matching composition uses h = ⌈log(40/ε)⌉ and local windows with aspect ratio less than 160/ε.The construction sets ρ = ε/[10(h+1)].
- Tightness: Local-window value information cannot generally achieve a (1 ± ε)-estimate when every admissible window has aspect ratio R < (ε^-1 − 1)/4.Two graphs can agree on every admissible interval value while having different global optima.
3 Dynamic Weight Reduction for MWM Weight
The reduction runs dynamic algorithms on O(ε^-1)-aspect-ratio weight windows and combines their outputs. It preserves key update-model properties and transfers weighted matching value guarantees from unweighted algorithms, including a bipartite application.
- Value reduction: The value composition lemma gives a dynamic reduction from polynomial aspect ratio to O(ε^-1)-aspect-ratio windows.It applies to graph classes closed under taking subgraphs because every window is a subgraph of the input.
- Dynamic implementation: The reduction preserves worst-case update time, determinism, and incremental or decremental operation.Local instances are fixed weight-induced subgraphs, so updates create only local insertions or deletions.
- Dynamic implementation: Each edge update affects at most 2h + 1 local instances, where h = ⌈log(20/ε)⌉.The affected local terms are adjusted before and after updating each local algorithm.
- Weight-to-cardinality reduction: Graph unfolding converts integer-weight bipartite MWM into unweighted MCM while preserving optimum value.For weights between 1 and R, the unfolded graph has at most Rn vertices and Rm edges.
- Weight-to-cardinality reduction: Theorem 3.3 lifts a dynamic (1 ± δ)-approximation algorithm for unit-weight bipartite MCM to a dynamic (1 ± ε)-approximation algorithm for bipartite MWM with polynomial aspect ratio.The lifted reduction preserves worst-case update time, determinism, and incremental or decremental operation.
- Application: For fixed ε, the BKS23 algorithm yields a randomized fully dynamic bipartite MWM algorithm with m^(1/2−Ωε(1)) worst-case update time.The guarantee holds with high probability against an adaptive adversary.
4 Dynamic Weight Reduction for Explicit Matchings
The section reduces dynamic weighted matching to local instances with bounded aspect ratio, then composes explicit local matchings into a global approximation while controlling recourse and update overhead.
- Reduction overview: O(ε−1)-aspect-ratio subroutines suffice to process a single O(ε−5)-aspect-ratio instance, improving the additive update overhead from eO(ε−6) to eO(ε−3).The improvement comes from lazy composition of local matchings.
- Bounded-aspect transformation: The transformation converts polynomial aspect ratio into O(ε−1) aspect ratio while preserving determinism and incremental or decremental updates.
- Lazy composition: Lazy composition maintains local matchings Mi and combines them through degree-two matching instances formed from Pi−1 ∪Mi.
- Analysis: The composed matching PL is a (1−O(ε))-MWM, with all Pi together requiring amortized recourse eO(ε−2) and eO(ε−3) update time for the composition structures.
- Bounded-aspect composition: The bounded-aspect composition lemma converts aspect ratio at most R into O(ε−5) while explicitly maintaining a (1−ε)-MWM with amortized recourse eO(ε−2).
- Applications: The reduction yields explicit (1−ε)-MWM algorithms for poly(n)-aspect-ratio graphs, including bipartite, bounded-degree, bounded-arboricity, and rounding applications.
A Low-Degree MWM Sparsifier for Low-Arboricity Graphs
The section constructs a low-degree subgraph by retaining edges marked by both endpoints among their heaviest incident edges, while preserving most maximum matching weight.
- Construction: Each vertex marks its O(α/ε) heaviest incident edges after rounding weights to powers of 1+ε/4, and H keeps edges marked by both endpoints.
- Weight preservation: If d>2α, marking d heaviest incident edges guarantees µw(H) ≥ (d−2α)/d · µw(G).
- Proof idea: The proof routes mass from matching edges omitted by H onto marked edges without decreasing edge weights, then uses the resulting fractional matching to certify weight preservation.
- Sparsifier guarantee: O(α/ε) degree and at least (1−ε/2)µw(F) weight are achieved by the dynamic sparsifier for graphs of arboricity at most α.The sparsifier has O(ε−1 log R) worst-case update time and causes O(1) edge changes.
- Dynamic maintenance: After updates, deterministic mark swaps restore the invariant, changing O(1) marks and therefore O(1) edges of H.