PaperlayerView exact revision on arXiv

Source-linked AI summary

Fully Dynamic Maximal Matching in Constant Update Time

Shay Solomon

arXiv:1604.08491v1cs.DS

TL;DR

Maintaining a maximal matching dynamically with constant update time remained an open problem. This paper uses a randomized level-rising approach to achieve O(t) total time in expectation and with high probability.

  • Problem

    Efficiently maintaining a maximal matching in a fully dynamic graph is a fundamental challenge, and achieving constant update time remained open.

    Source: §1.1 · p. 2

  • Method

    A randomized level-rising mechanism attempts to match a vertex at a higher level with a random lower-level neighbor, recursively settling a neighbor if needed.

    Source: §3.1 · p. 9

  • Results

    O(t) total time in expectation and with high probability maintains a maximal matching over any sequence of t edge updates, using O(n + m) space.

    Source: §4.5 · p. 16

  • Takeaways & Limitations

    The same update-time bound maintains 2-approximate maximal matching and 2-approximate maximal cardinality vertex cover.

    Source: §4.5 · p. 16

    Applicability of the level-rising mechanism to other dynamic graph problems is prospective and would require proper adjustments.

    Source: §2 · p. 7

Abstract

from arXiv · show

Baswana, Gupta and Sen [FOCS'11] showed that fully dynamic maximal matching can be maintained in general graphs with logarithmic amortized update time. More specifically, starting from an empty graph on $n$ fixed vertices, they devised a randomized algorithm for maintaining maximal matching over any sequence of $t$ edge insertions and deletions with a total runtime of $O(t \log n)$ in expectation and $O(t \log n + n \log^2 n)$ with high probability. Whether or not this runtime bound can be improved towards $O(t)$ has remained an important open problem. Despite significant research efforts, this question has resisted numerous attempts at resolution even for basic graph families such as forests. In this paper, we resolve the question in the affirmative, by presenting a randomized algorithm for maintaining maximal matching in general graphs with \emph{constant} amortized update time. The optimal runtime bound $O(t)$ of our algorithm holds both in expectation and with high probability. As an immediate corollary, we can maintain 2-approximate vertex cover with constant amortized update time. This result is essentially the best one can hope for (under the unique games conjecture) in the context of dynamic approximate vertex cover, culminating a long line of research. Our algorithm builds on Baswana et al.'s algorithm, but is inherently different and arguably simpler. As an implication of our simplified approach, the space usage of our algorithm is linear in the (dynamic) graph size, while the space usage of Baswana et al.'s algorithm is always at least $\Omega(n \log n)$. Finally, we present applications to approximate weighted matchings and to distributed networks.

1 Introduction

Efficiently maintaining a maximal matching under dynamic updates is a fundamental challenge, and improving logarithmic update time toward constant time remained open even for forests. The paper resolves this question for general graphs with a randomized constant-amortized-update-time algorithm.

1.1 Dynamic maximal matching.

  • O(t) total time in expectation and with high probability maintains a maximal matching in general graphs over t edge updates, resolving the open constant-update-time question.The bound applies starting from an empty graph on n fixed vertices.Source: §1.1 · p. 2
  • O(n + m) space improves on Baswana et al.’s O(n log n + m) usage, giving a logarithmic saving when m = O(n).The algorithm builds on their approach but is described as inherently different and simpler.Source: §1.1 · p. 2

1.2 Dynamic approximate matching and vertex cover.

  • Constant-update-time 2-MCM and 2-MCVC follow from maximal matching, and the 2-MCVC guarantee is essentially best possible under UGC.The algorithm also improves expected update time for 8-MWM from O(log n log ∆) to O(log ∆).Source: §1.2 · p. 3, §1.3 · p. 3

1.3 Additional applications.

  • In the distributed setting, the algorithm achieves a small constant average number of messages per update, where message counts can otherwise reach O(n).Only the endpoints of an updated edge wake up; O(1) communication rounds trivially suffice for updating a maximal matching.Source: §1.3 · p. 3

1.4 Our and Previous Techniques.

  • A lazy level-maintenance scheme avoids BGS’s fading waves and per-level counters, using a level-rising mechanism to choose a higher level on the fly.The algorithm still uses O(log n) levels, but changes a vertex’s level only when necessary.Source: §1.3 · p. 4

2 A High-Level Technical Overview

Maintaining maximality by scanning for replacement mates can be costly, while earlier orientation and level schemes still incur logarithmic work. The paper’s lazy level-rising approach avoids maintaining those level inequalities and uses recursive random settling to achieve efficient repairs.

2 A High-Level Technical Overview

  • Randomly choosing a replacement neighbor still has expected amortized cost O(deg(z)+deg(w)), which can reach O(n) when deg(w) is large.Restricting choices to low-degree neighbors does not solve the problem when there are too few such neighbors or when a chosen neighbor is already matched.Source: §2 · pp. 4–5
  • BGS orients edges toward lower-level endpoints so vertices can scan outgoing neighbors, but orienting toward lower out-degree directly can trigger long cascades of edge flips.This orientation reduces the candidate search from all neighbors to outgoing neighbors.Source: §2 · p. 5
  • BGS maintains level inequalities across higher levels; counters and level searches cost O(log n), while its fading-wave analysis bounds cascades logarithmically.The stronger invariant ensures that after a one-level fall, neighbors rise by at most one level.Source: §2 · pp. 5–6
  • The new scheme changes a vertex’s level only after incident matched-edge updates, avoiding BGS’s inequalities but leaving its out-degree unbounded by its level.When scanning is affordable, the vertex can be handled deterministically; otherwise the algorithm uses level rising.Source: §2 · p. 6
  • When scanning is too costly, the vertex rises gradually to a threshold level and chooses a random lower-level outgoing neighbor from a sufficiently large candidate set.The expected matching cost compensates for the rising-process scan cost.Source: §2 · p. 6
  • If the chosen neighbor is matched, it must rise to the same level; recursive settling handles the resulting edge flips and reprocessing, bypassing φ_v counters.The authors anticipate that, with adjustments, level rising may apply to other dynamic graph problems.Source: §2 · pp. 6–7

3 The Update Algorithm

The update algorithm maintains a level-based orientation and matching, repairing exposed free vertices through deterministic or randomized settling. When w′ is unmatched, it invokes `handle-free(w′)`.

3.1 Invariants and data structures.

  • Matched edges join same-level vertices, while free vertices have level -1 and out-degree 0, ensuring the maintained matching is maximal.The algorithm orients edges from higher-level to lower-level vertices.Source: §3.1 · p. 7
  • On insertion, two free endpoints are matched at level 0; deleting a matched edge makes both endpoints temporarily free and invokes handle-free on each.Source: §3.1 · p. 8
  • handle-free uses deterministic settling when the out-degree is below 3^(ℓv+1), scanning for a free neighbor; otherwise it invokes random-settle.If no free neighbor is found, deterministic settling leaves v free at level -1; otherwise it matches v with a free neighbor and sets both levels to 0.Source: §3.1 · pp. 8–9
  • random-settle raises v to the first level ℓ* with φv(ℓ*+1) < 3^(ℓ*+1), then samples a lower-level outgoing neighbor and raises that neighbor to ℓ*.Computing ℓ* and updating v’s level take O(3^ℓ*) time; if the neighbor’s resulting out-degree is at least 3^(ℓ*+1), the procedure recursively settles that neighbor at a higher level.Source: §3.1 · pp. 10–11
  • Keeping matched-edge endpoints at the same level makes both endpoints lower-level than a rising vertex, enabling the charging argument for induced deletions.A sampled neighbor may already be matched, so matching it can displace its existing matched edge.Source: §3.1 · p. 11
  • If w′ is not matched to any vertex, the algorithm invokes Procedure handle-free(w′).Source: §3.1 · p. 12

4 Analysis

The analysis charges update work to matched-edge epochs, bounding each epoch’s cost by its level and then bounding recursive induced costs. This accounting yields the stated constant amortized update time and linear-in-graph-size space.

4.1 Invariants.

  • Temporarily free vertices may be ignored during deterministic settling, so subsequent handle-free calls process them and restore matching as needed.The algorithm handles every vertex that becomes temporarily free through appropriate calls to handle-free.Source: §4.1 · p. 12

4.2 Epochs.

  • An epoch is a maximal interval in which a matched edge remains matched; at level ℓ > 0, its initiating vertex has out-degree from 3^ℓ up to but not including 3^(ℓ+1).The mate is chosen uniformly among outgoing neighbors, so the edge becomes matched with probability at most 1/3^ℓ.Source: §4.2 · pp. 12–13

4.3 Re-distributing the computation costs to epochs.

  • The analysis redistributes update-step work to created and terminated epochs, bounding each level-ℓ epoch’s charged computation by O(3^ℓ).Recursive-call debt is bounded by the next examined vertex’s out-degree and is absorbed by a subsequent higher-level epoch.Source: §4.3 · pp. 13–14

4.4 Natural versus induced epochs.

  • Each random-settle recursion creates an epoch at a higher level, and the induced epochs it terminates have strictly lower levels; recursive cost is therefore O(3^ℓ) for a level-ℓ epoch.A created epoch terminates at most two lower-level epochs.Source: §4.4 · p. 16

4.5 Bounding the algorithm’s runtime.

  • The runtime analysis bounds expected total cost by O(t) and the high-probability cost by O(t + n log n); the theorem gives O(t) with high probability.The final-graph edge deletions used in the argument add at most a factor of two to the update sequence.Source: §4.5 · p. 16
  • O(n + m) space is linear in the dynamic graph size.The theorem specifies m as the dynamic number of edges.Source: §4.5 · p. 16
  • O(t) total time in expectation and with high probability, with O(n + m) space, maintains maximal matching over any t edge updates.The theorem also states maintenance of 2-MCM and 2-MCVC.Source: §4.5 · p. 16

A Tables and Pseudocode

The supplied material identifies Table 1 as a comparison of dynamic maximal-matching results and gives a few edge-insertion pseudocode steps. It does not provide the table’s result values.

A Tables and Pseudocode

  • Table 1 compares prior and new dynamic maximal-matching results; t counts updates for [3], while α bounds arboricity for [22, 12].The caption defines arboricity as the minimum number of edge-disjoint forests partitioning the graph.Source: Table 1 · p. 18
  • The insertion pseudocode orients an edge from the endpoint with greater or equal level toward the other endpoint.The reverse orientation is used when the second endpoint has the greater level.Source: A Tables and Pseudocode · p. 18
  • When both endpoints are free, the insertion procedure matches them.Figure 1 is captioned as handling insertion of edge (u, v).Source: A Tables and Pseudocode · p. 18, Figure 1

B Proof of Lemma 4.6

The proof controls recursive work through epoch lifetimes and counts, yielding a high-probability total cost of O(t+n log n). It bounds how often short epochs occur and how many long natural epochs can be charged at each level.

B Proof of Lemma 4.6

  • Among q natural level-ℓ epochs lasting at least δ, q ≤ 2tℓ/δ because each defining deletion is associated with at most two epochs.Here tℓ counts edge deletions at level ℓ.Source: B Proof of Lemma 4.6 · pp. 19, 22
  • For a level-ℓ epoch, each possible uninterrupted duration k has probability 1/|O_u^l| ≤ 1/3^ℓ, even conditioned on the epoch's level being ℓ.The duration is uniformly distributed over the outgoing edges present when the epoch begins.Source: B Proof of Lemma 4.6 · p. 23
  • The probability that an epoch's uninterrupted duration is at most k is at most k/3^ℓ, independently of earlier epochs' durations.This bound still holds conditioned on the epoch's level being ℓ.Source: B Proof of Lemma 4.6 · p. 23
  • If ¬Aℓ, then Yℓ < c(tℓ + 3^ℓ log n), bounding recursive work at that level.The proof treats the exceptional event Aℓ as rare; its probability is bounded by 8/(3n^4).Source: B Proof of Lemma 4.6 · pp. 23–24
  • O(t+n log n) bounds the total recursive cost Y with high probability.The per-level analysis bounds Yℓ unless a rare bad event occurs.Source: B Proof of Lemma 4.6 · pp. 24–25

B.1 Justifying the assumption

The analysis justifies its assumption by charging excess induced-epoch costs to natural epochs at the same level. A revised level parameter then preserves the required recursive cost bound.

B.1 Justifying the assumption

  • When Tℓ > 2Xℓ, induced epochs outnumber natural epochs at level ℓ, so the analysis must account for that case.The proof argues these levels can be disregarded in the runtime analysis by charging their costs to higher levels.Source: §B.1 · p. 25
  • A one-to-one mapping pairs every natural level-ℓ epoch with an induced epoch, allowing its cost to be charged to that induced epoch.The recursive cost is redefined to include corresponding natural epochs as well as induced epochs.Source: §B.1 · p. 25
  • Changing the level base from 3 to 5 gives the recurrence ˆCℓ ≤ 4ˆCℓ−1 + O(5^ℓ), which resolves to ˆCℓ = O(5^ℓ).The analysis consequently uses log5(n−1) levels.Source: §B.1 · p. 25

C Improving the high probability bound

The analysis handles every update-sequence length without assumptions, with a high-probability runtime bound tailored to whether t is at least Ω(n^ε). It improves the bound by limiting vertex levels while keeping the total runtime increase to a constant factor.

C Improving the high probability bound

  • For t=Ω(n^ε), runtime exceeds O(t) with probability polynomially small in n; for smaller t, that probability is polynomially small in t.The analysis also addresses the regime n/2 ≤ t = o(n log n), rather than assuming t is at least Ω(n log n).Source: C Improving the high probability bound · p. 25
  • The earlier bound of O(t + n log t) with probability O(log n/t^4) is not the desired high-probability guarantee.The analysis therefore changes the events and claims used in the tail bound.Source: C Improving the high probability bound · p. 26
  • Bounding all vertex levels improves the high-probability runtime bound while increasing total runtime by at most a constant factor.The section identifies this level bound as the key insight for improving the guarantee.Source: C Improving the high probability bound · p. 26
  • The algorithm caps rising at ℓmax, preserving the lower bound on φv(ℓ*) even though the previous upper bound may no longer hold.The adjusted loop stops when ℓ* reaches ℓmax.Source: C Improving the high probability bound · p. 26
  • At the maximum level, epochs become stagnant: outgoing edges do not flip, and large rising costs can be charged to incident-edge deletions.A maximum-level epoch can end only when its matched edge is deleted; at least Ω(D) incident-edge deletions pay for an O(D) rising cost.Source: C Improving the high probability bound · p. 27

D Applications

The paper applies its dynamic matching approach to approximate weighted matching and distributed networks. These applications yield an 8-MWM with expected amortized update time O(log Δ) and distributed maximal matching with constant amortized message complexity.

Dynamic approximate MWMs

  • An 8-MWM can be maintained with expected amortized update time O(log Δ), shaving a factor of log n from the prior update time.The prior approach maintains weight buckets and uses the maximal-matching algorithm of [3] for each bucket; the stated bound is O(log Δ), where Δ is the ratio of maximum to minimum edge weights.Source: D Applications · p. 28

Distributed networks

  • A distributed maximal matching can be maintained with constant amortized message complexity under the CONGEST model.The same theorem includes 2-MCM and 2-MCVC.Source: D Applications · p. 28
  • Optimizing the constant in the amortized message complexity remains open.The distributed approach uses O(1) communication rounds after an update, O(log n)-size messages, and may send O(n) messages on an individual update.Source: D Applications · p. 28
Loading 1604.08491v1…