PaperlayerView exact revision on arXiv

Source-linked AI summary

The Power of Local Marginals: An $O(\varepsilon^{-1})$-Aspect-Ratio Reduction for Dynamic Weighted Matching

Jiale Chen

arXiv:2608.27805v1cs.DS

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.

    Source: §1 · pp. 2–3

  • 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).

    Source: §1 · pp. 3–4

  • 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.

    Source: §1 · pp. 3–4

  • 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.

    Source: §1 · p. 4

    The value lower bound applies only to reductions using local MWM values, while the matching lower bound assumes adversarial choices of local MWMs.

    Source: §1 · p. 4

Abstract

from arXiv · show

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.Source: §1 · p. 2

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.Source: §1 · pp. 2–3

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).Source: §1 · p. 3

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.Source: §1 · pp. 3–4

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).Source: §1 · p. 4

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.Source: §1 · p. 4

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).Source: §1 · p. 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].Source: §2 · p. 5
  • 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.Source: §2 · p. 5
  • 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.Source: §2 · p. 5

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.Source: §2.1 · p. 6
  • 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.Source: §2.1 · p. 6

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.Source: §2.2 · p. 7
  • 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)].Source: §2.2 · p. 7

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.Source: §2.3 · p. 8

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.Source: §3 · p. 8

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.Source: §3 · pp. 8–9
  • 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.Source: §3 · p. 9

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.Source: §3.1 · p. 9
  • 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.Source: §3.1 · p. 9

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.Source: §3.2 · p. 10

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.Source: §4 · p. 11

Bounded-aspect transformation

  • The transformation converts polynomial aspect ratio into O(ε−1) aspect ratio while preserving determinism and incremental or decremental updates.Source: §4.1 · p. 11, §4.3 · p. 14

Lazy composition

  • Lazy composition maintains local matchings Mi and combines them through degree-two matching instances formed from Pi−1 ∪Mi.Source: §4.1 · p. 11

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.Source: §4.2 · pp. 12–14

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).Source: §4.2 · p. 13

Applications

  • The reduction yields explicit (1−ε)-MWM algorithms for poly(n)-aspect-ratio graphs, including bipartite, bounded-degree, bounded-arboricity, and rounding applications.Source: §4.3 · p. 14, §4.4 · p. 15

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

Weight preservation

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.Source: A Low-Degree MWM Sparsifier for… · p. 19

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.Source: A Low-Degree MWM Sparsifier for… · p. 19

Dynamic maintenance

Loading 2608.27805v1…