Source-linked AI summary
Fully dynamic maximal matching in O(log n) update time
Surender Baswana, Manoj Gupta, Sandeep Sen
TL;DR
The paper addresses efficient maintenance of maximal matching under dynamic edge insertions and deletions. It presents a randomized level-based data structure with random mate selection, achieving O(log n) expected amortized update time while correcting the prior analysis. The approach also yields a tight factor-two approximation guarantee and related maintenance consequences.
Problem
The paper studies how to maintain maximal matching efficiently when graph edges are inserted or deleted, rather than recomputing after every update.
Method
The randomized algorithm partitions vertices into levels, uses local edge information to adjust levels, and selects random mates while maintaining maximal matching.
Results
O(log n) expected amortized time per update is achieved, with total time O(t log n + n log2 n) with high probability.
Takeaways & Limitations
The maintained maximal matching provides a factor-two approximation to maximum matching, and the paper shows this factor is tight for the algorithm.
Takeaways & Limitations
The analysis must account for update sequences whose distribution depends on the current matching and the algorithm's random choices.
Abstract
from arXiv · showhide
We present an algorithm for maintaining maximal matching in a graph under addition and deletion of edges. Our data structure is randomized that takes O(log n) expected amortized time for each edge update where n is the number of vertices in the graph. While there is a trivial O(n) algorithm for edge update, the previous best known result for this problem for a graph with n vertices and m edges is O({(n+ m)}^{0.7072})which is sub-linear only for a sparse graph. For the related problem of maximum matching, Onak and Rubinfield designed a randomized data structure that achieves O(log^2 n) amortized time for each update for maintaining a c-approximate maximum matching for some large constant c. In contrast, we can maintain a factor two approximate maximum matching in O(log n) expected time per update as a direct corollary of the maximal matching scheme. This in turn also implies a two approximate vertex cover maintenance scheme that takes O(log n) expected time per update.
1 Introduction
The paper addresses maintaining maximal matching in dynamic graphs, where edge insertions and deletions require efficient updates. It corrects the prior analysis of an existing randomized algorithm while preserving its performance bounds and related approximation consequences.
- Problem: A maximal matching guarantees a 2-approximation of maximum matching, although computing one statically takes O(m + n) time.The paper focuses on maintaining this weaker matching efficiently in a changing graph.
- Motivation: Dynamic graph algorithms update solutions after each edge insertion or deletion instead of recomputing from scratch.The goal is to achieve update time much smaller than rerunning the best static algorithm.
- Prior work: O(log n) expected amortized time per edge update was achieved by the earlier fully dynamic maximal-matching algorithm.For t updates, its total time is O(t log n + n log2 n) with high probability.
- Consequences: The maximal-matching algorithm also yields a two-approximate vertex-cover maintenance result and supports approximate maximum-weight matching.These are presented as consequences or applications of the maintained matching scheme.
- Contribution: The paper provides an alternate proof because the earlier analysis relied on a lemma that is not true in general.The algorithm itself is unchanged, and the corrected analysis preserves the claimed update-time bounds.
2 An overview
The overview develops progressively faster fully dynamic algorithms for maximal matching. The final algorithm uses multiple vertex levels and randomized mate selection to achieve expected amortized O(log n) update time.
- Basic approach: A matching is maximal exactly when no graph edge has two free endpoints.This condition motivates repairing the matching locally after updates.
- Basic approach: When an inserted edge joins two free vertices, it is added to the matching; deleting an unmatched edge requires no action.Deleting a matched edge may require searching both endpoint neighborhoods for free vertices.
- Two-level algorithm: O(√n) expected amortized update time is obtained by combining random-mate selection with a trivial algorithm using a two-level vertex partition.High-ownership vertices use random mates, while low-ownership vertices use the trivial method.
- Final algorithm: O(log n) expected amortized update time is achieved by a finer partition of vertices into multiple levels.The final algorithm maintains an invariant governing when vertices rise or fall between levels.
- Final algorithm: A vertex rises when its incident edges from lower levels are sufficiently numerous and then selects a random edge from that set as its matched edge.Vertices use local neighborhood information to reach a global equilibrium in which no vertex has an incentive to change levels.
- Organization: The paper presents the final algorithm after first introducing a simpler, less efficient fully dynamic algorithm.The tightness example and subsequent notation support the analysis of the final construction.
3 Preliminaries
The preliminaries define the level-based representation of the maintained matching and introduce asymmetric random-walk analysis used in the algorithms' proofs.
- Level representation: Matched edges are represented as tuples (u, v, ℓ), with both endpoints matched at the same level ℓ.The algorithm partitions vertices among levels and defines an edge's level as the maximum level of its endpoints.
- Random-walk tool: The analysis uses a discrete asymmetric random walk whose right and left moves have probabilities p and q = 1 − p, respectively, with p > q.Each move is independent of the previous moves.
- Random-walk tool: The random-walk lemma bounds the probability that a walk starting ℓ units from the origin reaches the origin within L steps.The proof is sketched in the appendix and supports later algorithmic analysis.
4 Fully dynamic algorithm with expected amortized O(√n) time per update
The algorithm maintains a maximal matching using two vertex levels, edge ownership, and settling procedures that restore invariants after updates. Epoch-based analysis bounds total processing over t updates by O(t√n + n log n) with high probability, while the full multilevel approach achieves expected amortized O(log n) update time.
- Algorithm design: Level 0 uses edge ownership and NAIVE-SETTLE, while level 1 uses RANDOM-SETTLE with a uniformly random owned mate.Vertices move between levels when ownership thresholds are violated, and settling restores the invariants.
- Algorithm invariants: The algorithm maintains three invariants: every level-1 vertex is matched, free level-0 vertices have only matched neighbors, and matched-edge endpoints share a level.The first invariant ensures that the maintained matching is maximal after every update.
- Update handling: Deleting a matched level-1 edge can create many dirty vertices when an endpoint moves to level 0, requiring neighboring level-0 vertices to be scanned and possibly reprocessed.This is the main source of potentially extensive work during deletion.
- Epoch analysis: Level-0 epochs cost O(√n), whereas level-1 epochs cost O(n); each level-1 epoch induces at most two level-0 epochs.This relationship allows the analysis to charge induced lower-level work to higher-level epochs.
- High-probability analysis: A level-1 epoch is bad with probability 1/3, and with probability at least 1−1/n^2 bad epochs exceed good epochs by at most 2 log^2 n.These bounds control the aggregate cost of level-1 epochs over any sequence of t updates.
- Overall bound: The total cost for t updates is O(t√n + n log n) with high probability, while the resulting fully dynamic algorithm achieves expected amortized O(log n) time per edge update.The high-probability bound is stated for the analyzed epoch scheme; the final multilevel construction yields the logarithmic expected amortized guarantee.
5 Fully dynamic algorithm with expected amortized O(log n) time per update
The fully dynamic algorithm maintains vertices across logarithmically many levels using directed edge ownership and randomized settling. Its invariants ensure maximality while level changes update neighboring vertices’ potential values efficiently.
- Levels and ownership: The algorithm partitions vertices among ⌊log4 n⌋+2 levels, from −1 through ⌊log4 n⌋, with level −1 containing vertices that own no edges.A vertex at level i owns at least 4^i edges.
- Levels and ownership: Each edge is owned by exactly one endpoint: the higher-level endpoint, with ties broken by the algorithm.Each vertex stores its owned edges in a dynamic hash table and tracks incident edges from higher or equal levels that it does not own.
- Invariants and level changes: For a vertex v at level i, φv(j) counts edges v could own at level j; v rises to the highest j where φv(j) ≥ 4^j.The algorithm maintains φv(j) < 4^j for every j above v’s current level.
- Invariants and level changes: The three invariants require nonnegative-level vertices to be matched, prohibit φv(j) from reaching 4^j above the current level, and place matched-edge endpoints at the same level.These conditions imply that every free vertex is at level −1 and has only matched neighbors.
- Potential maintenance: Neighbor rises decrement φ values over intervals, while neighbor falls increment one φ value; total decrement work is bounded by total increment work.A decrement may cost O(log n), whereas an increment costs O(1), and nonnegativity yields the aggregate bound.
- Randomized settling: When an invariant is violated, GENERIC-RANDOM-SETTLE moves a vertex, updates ownership, and selects a random owned edge to establish a new mate.The procedure informs affected neighbors, acquires eligible edges, updates potentials, and recursively settles the selected neighbor when needed.
5.2 Handling edge updates by the fully dynamic algorithm
PROCESS-FREE-VERTICES restores the invariants after edge updates by processing free vertices from higher to lower levels. Vertices either settle using owned edges or fall one level, and termination restores maximality globally.
- Processing free vertices: PROCESS-FREE-VERTICES receives free vertices as ordered pairs (x, i) and processes them in decreasing level order.A queue Q stores vertices by level, and the procedure scans levels from L0 down to 0.
- Edge updates: After deleting a matched edge, both endpoints are submitted to PROCESS-FREE-VERTICES at their common level.Deleting an unmatched edge only removes it from the relevant data structures after updating potentials.
- Edge updates: After inserting an edge, the algorithm increments endpoint potentials and raises the highest endpoint that reaches the threshold φ(i)=4^i.If both endpoints qualify, only the endpoint with the higher attainable level rises, restoring both invariants.
- Free-vertex handling: The falling process forms a wave through successive levels until free vertices reach level −1 and maximality is restored.Lemma 5.5 states that termination leaves no free vertices at nonnegative levels and restores all invariants globally.
5.3 Analysis of the algorithm
The analysis bounds the cost of maintaining the matching by organizing updates into epochs across O(log n) levels, controlling bad epochs probabilistically, and charging computation to good natural epochs. This yields O(t log n) expected total time and O(t log n + n log2 n) time with high probability for t updates.
- Epoch and level structure: O(4^i) computation is associated with an epoch at level i.This bound is used to charge the cost of epoch trees during the high-probability analysis.
- High-probability analysis: A created epoch at level i can terminate at most two epochs at lower levels, enabling a forest-based accounting of terminated epochs.The forest also associates at most four lower-level epochs with each node.
- High-probability analysis: 1/3 is an upper bound on the probability that a newly created epoch is bad, independently of prior updates and random bits.The argument uses the random mate and the update sequence associated with the epoch.
- High-probability analysis: 2 log2 n bounds the excess of bad over good epochs at every level with probability at least 1 − (log n)/n2.This bound supports mapping bad epochs to good epochs and charging the resulting computation.
- Final bound: O(t log n) expected total time and O(t log n + n log2 n) time with high probability hold for any sequence of t updates.The result starts from an empty graph on n vertices.
5.4 Proof of Lemma 5.8
The proof of Lemma 5.8 establishes that the update sequence associated with an epoch is independent of the random mate selected when the epoch is created. It does so by showing that higher-level matching distributions are unaffected by lower-level differences.
- Proof strategy: The algorithm maintains a probability distribution over possible maximal matchings as updates are processed.This distributional view is used to compare executions beginning from different possible matchings.
- Proof strategy: The independence argument is required because an epoch’s associated update sequence depends on the current matching and the algorithm’s random bits.The paper identifies this dependence as making the final algorithm’s analysis more complex than the two-level algorithm’s analysis.
- Higher-level invariance: For matchings that agree above level i, φ_v(j) is identical for every vertex v and level j > i.Consequently, the vertex sets and lower-level neighborhoods relevant to higher levels are identical.
- Proof strategy: The matching is updated in decreasing level order, and completed higher-level updates remain unchanged while lower levels are processed.This ordering prevents later lower-level changes from altering the higher-level matching.
- Higher-level invariance: Matching updates at levels above i have identical probability distributions in executions starting from any two matchings that agree above level i.The statement extends from one update to any sequence of t updates by induction.
6 A tight example
The paper gives an update sequence showing that the algorithm’s factor-two approximation is tight. A complete graph on V is matched first, while later edges connecting V to W leave the maintained matching unchanged even though a perfect matching exists.
- Construction: n/2 is the size of any maximal matching in the complete graph formed by V.The first update phase creates this complete subgraph and produces a maintained matching of size n/2.
- Construction: The added edges (v_i, w_i) do not change the maintained matching because each v_i owns them while each w_i remains at level −1.The maintained matching therefore remains the matching formed during the first phase.
- Tightness: n is the maximum matching size after the second phase, exactly twice the maintained matching size.Thus the example realizes the algorithm’s factor-two approximation bound.
7 Postscript
The paper presents a randomized fully dynamic maximal-matching algorithm with expected amortized O(log n) update time, while identifying open questions about randomization and constant-time updates.
- Expected amortized O(log n) time is achieved per edge insertion or deletion for fully dynamic maximal matching.
- Deterministic (2 + ǫ)-approximate matching with amortized O(poly(log n, 1/ǫ) update time later addressed whether randomization is essential.
- The algorithm’s explicit maintenance of φ_v(j) preserves an invariant linking vertex levels to incident edges, but imposes Θ(log n) update overhead.
- Solomon’s algorithm removes this overhead through a lazy approach and new ideas, but loses the original algorithm’s independence property.
- Dynamic matching with approximation less than 2 and dynamic weighted matching subsequently received further progress.
- Maintaining c-approximate maximum matching for c < 2 in o(n) update time remains an interesting challenge under conditional lower-bound considerations.
Proof of Lemma 5.15
The proof applies conditional probability to mutually exclusive events, expressing the target probability through their weighted contributions.
- Conditional probability is expanded using Pr[A | B_i] · Pr[B_i].
- The contributions over the events B_i are combined because the events are mutually exclusive.
- The resulting expression is ρ · Pr[∪_i B_i] = ρ · Pr[C].
Proof of Lemma 5.16
The proof begins from the independence of A and X and uses that independence uniformly for each x in X.
- A is independent of X.
- The argument applies the independence assumption separately for every x ∈ X.
- The lemma’s proof therefore conditions its reasoning on individual elements of X rather than treating X only as a whole.
Proof of Lemma 3.1
The proof relates asymmetric random walks to a restricted Gambler’s ruin problem and bounds ruin probability using the standard unrestricted problem.
- The asymmetric random walk is presented as a special case of the Gambler’s ruin problem with win probability p and loss probability q = 1 − p.
- A textbook result is cited as a concise self-contained proof of the standard Gambler’s ruin lemma.
- For p > q, the standard Gambler’s ruin lemma gives the probability that Player 1 is ruined.
- Restricting the game to L rounds prevents Player 2 from being ruined when L < c′.
- The restricted problem has strictly lower Player 1 ruin probability than the unrestricted problem.
- The restricted game maps to a walk starting c units right of the origin and ending at the origin or after L steps.