Source-linked AI summary
Simple Deterministic Algorithms for Fully Dynamic Maximal Matching
Ofer Neiman, Shay Solomon
TL;DR
Fully dynamic maximal matching had a deterministic O(n) update baseline, with no known deterministic improvement. This paper presents a simple deterministic algorithm with O(√m) worst-case updates and a 3/2-approximate maximum-cardinality matching.
Problem
No deterministic algorithm was known to maintain a fully dynamic maximal matching faster than the naive O(n) update time, even with amortized bounds.
Source: §1 · p. 2Method
A simple deterministic dynamic algorithm maintains a maximal matching using bounded edge orientations to pass vertex status along outgoing edges and track free neighbors.
Source: §1 · p. 2, §1.2 · p. 4Results
O(√m) worst-case update time maintains a 3/2-approximate MCM; when c=Ω(log n), low-arboricity updates take amortized O(c) time.
Source: §1 · p. 2Takeaways & Limitations
The vertices participating in the maximal matching also form a 2-approximate vertex cover.
Source: §1 · p. 2The setup assumes an initially empty graph, with each update adding or deleting one edge.
Source: §3 · p. 4
Abstract
from arXiv · showhide
A maximal matching can be maintained in fully dynamic (supporting both addition and deletion of edges) $n$-vertex graphs using a trivial deterministic algorithm with a worst-case update time of O(n). No deterministic algorithm that outperforms the na\"{\i}ve O(n) one was reported up to this date. The only progress in this direction is due to Ivkovi\'{c} and Lloyd \cite{IL93}, who in 1993 devised a deterministic algorithm with an \emph{amortized} update time of $O((n+m)^{\sqrt{2}/2})$, where $m$ is the number of edges. In this paper we show the first deterministic fully dynamic algorithm that outperforms the trivial one. Specifically, we provide a deterministic \emph{worst-case} update time of $O(\sqrt{m})$. Moreover, our algorithm maintains a matching which is in fact a 3/2-approximate maximum cardinality matching (MCM). We remark that no fully dynamic algorithm for maintaining $(2-\eps)$-approximate MCM improving upon the na\"{\i}ve O(n) was known prior to this work, even allowing amortized time bounds and \emph{randomization}. For low arboricity graphs (e.g., planar graphs and graphs excluding fixed minors), we devise another simple deterministic algorithm with \emph{sub-logarithmic update time}. Specifically, it maintains a fully dynamic maximal matching with amortized update time of $O(\log n/\log \log n)$. This result addresses an open question of Onak and Rubinfeld \cite{OR10}. We also show a deterministic algorithm with optimal space usage, that for arbitrary graphs maintains a maximal matching in amortized $O(\sqrt{m})$ time, and uses only $O(n+m)$ space.
1 Introduction
The paper improves deterministic fully dynamic matching beyond the O(n) update-time baseline, with a worst-case O(√m) guarantee and a 3/2-approximate maximum matching. It also gives faster bounds for low-arboricity graphs and an optimal-space variant.
1 Introduction
- O(√m) worst-case update time maintains an explicit maximal matching in arbitrary dynamic graphs, improving the prior O(n) deterministic baseline.Source: §1 · p. 2
1.1 Related Work
- The work improves Ivković and Lloyd for all m and beats the prior deterministic O(n) bound even when amortized time is allowed.Source: §1 · p. 2
1 Introduction
- The maintained matching is a 3/2-approximate MCM because it has no augmenting paths of length 3.Source: §1 · p. 2
- The result gives a data structure for dynamic maximal matching in arbitrary graphs, but not a 3/2-approximate MCM, with optimal space O(n + m).Source: §1 · p. 2
- For low-arboricity graphs, the algorithm gives a 2-approximation with sub-logarithmic update time, addressing an open question in [19].Source: §1 · p. 2
1.2 Overview of the Algorithm
- For low arboricity, vertices send status information along outgoing edges of a bounded orientation; incoming-neighbor information remains authentic, while outgoing-neighbor information is checked on demand.Source: §1.2 · p. 4
2 Preliminaries
The preliminaries define matching terminology and relate the absence of short augmenting paths to approximation quality.
2 Preliminaries
- A matching is a set of vertex-disjoint edges; an MCM has maximum cardinality, while a maximal matching is maximal under inclusion and is a 2-approximation.Source: §2 · p. 4
- An augmenting path is alternating and joins two different free vertices; no augmenting path of length at most 3 implies a 3/2-approximate MCM.Source: §2 · p. 4
3 General Graphs
For general dynamic graphs, the section presents a deterministic algorithm that maintains a maximal matching and a 3/2-approximate maximum cardinality matching with worst-case update time O(sqrt(n + m)). It uses bounded free-vertex degrees and short augmenting-path repairs to preserve these properties.
3.1 Data Structures
- Free-neighbor structures support constant-time membership checks and updates, while extracting a free neighbor takes O(sqrt(n)) time.The data structures also store the matching, each vertex's neighbors and degree, and a max-heap of free vertices keyed by degree.Source: §3.1 · pp. 4–5
3.2 Algorithm
- Each edge update is handled in a round that preserves maximality, a bound on newly free vertices' degrees, and the absence of length-3 augmenting paths.The algorithm's maintained matching has no augmenting paths of length 3.Source: §3.2 · pp. 5–6
3.2.1 Edge Addition
- For an edge insertion, the algorithm handles four endpoint-matching cases; when both endpoints are free, it matches them, and when a length-3 augmenting path appears, it flips the matching along that path.Insertion takes O(sqrt(n + m)) time and preserves the stated invariants.Source: §3.2.1 · pp. 6–7
3.2.2 Edge Deletion
- When a matched edge is deleted, the algorithm searches for a replacement match or a length-3 augmenting path; if an endpoint has high degree, it uses a low-degree surrogate.Matched-edge deletion is handled in O(sqrt(n + m)) time while preserving the relevant invariants.Source: §3.2.2 · pp. 7–8
3.2.3 Bounding the Degree of Free Vertices
- The algorithm processes a constant number of problematic free vertices per round, prioritizing the highest-degree one, so each is corrected before violating the degree bound.A problematic vertex's degree cannot change while it remains problematic; the proof shows it is corrected before the assumed violation can persist.Source: §3.2.3 · pp. 8–9
3 General Graphs
- O(sqrt(n + m)) worst-case update time maintains a maximal matching that is also a 3/2-approximate maximum cardinality matching.The bound is per edge update, with m denoting the current number of edges.Source: §3 · p. 4, §3.2.3 · p. 9
4 Low Arboricity Graphs
For bounded-arboricity graphs, the section reduces dynamic maximal matching to maintaining a bounded-outdegree orientation. Combining orientation maintenance with matching bookkeeping yields amortized update bounds, including a sub-logarithmic bound for sufficiently small arboricity.
4 Low Arboricity Graphs
- A ∆-orientation directs each edge so every vertex has out-degree at most ∆; arboricity at most c implies a c-orientation via the forest decomposition of Nash and Williams.The section defines bounded-arboricity graphs as uniformly sparse and includes planar, bounded-genus, bounded-tree-width, and fixed-minor-excluding graphs.Source: §4 · p. 9
4.1 Reduction from Matchings to Orientations
- The reduction uses D(u) for outgoing neighbors and F(u) for free neighbors not in D(u), letting each vertex learn the status of vertices pointing to it.The orientation bounds |D(u)| by ∆; the data structures support insertion, deletion, and extraction in amortized O(1) time.Source: §4.1 · p. 10
- After each orientation update, the algorithm restores consistency of F and D; inserting an edge checks whether it can join the matching and updates affected free-neighbor sets in O(∆) time.Deleting a matched edge searches the affected vertices’ D and F sets; the D scan costs O(∆), while extracting a free vertex from F is amortized O(1).Source: §4.1 · p. 10
- For any ∆>2c, Theorem 4.3 maintains a maximal matching in amortized time O(∆ + log n / log(∆/c)).The reduction adds O(∆) matching operations to the orientation-maintenance work.Source: §4.1 · p. 11
- When c ≤ log^(1−ε)n for constant ε>0, the amortized update time is O(log n / log log n); for c = Ω(log n), it is O(c).The passage also states the sub-logarithmic bound for any c = o(log n).Source: §4.1 · p. 11
5 Maximal Matching Using Optimal Space
The paper implements its bounded-arboricity algorithm in O(n + m) space without more than a constant-factor increase in amortized update time. A staging strategy extends the result to arbitrary graphs, maintaining a maximal matching in amortized O(√m) time.
5 Maximal Matching Using Optimal Space
- The implementation keeps neighbor, outgoing-neighbor, and free incoming-neighbor lists, reuses one smart array, and bounds list sizes relative to each vertex's degree.N(u) and F(u) can contain redundant elements; D(u) is kept authentic.Source: §5 · p. 12
- Deleted edges fund authentication of stale N(u) lists with tokens, while searches in the outgoing-neighbor lists check whether candidate edges remain.The stated authentication cost is covered by tokens placed on deleted edges.Source: §5 · p. 12
- When |F(u)| ≥ 3 deg(u), a partial token-funded authentication process reduces its size to at most 2 deg(u); since |N(u)| ≤ 2 deg(u), at least deg(u) elements are removed.Each removed element had O(1) tokens for its removal.Source: §5 · p. 13
- The bounded-arboricity algorithm can be implemented in O(n + m) space without increasing amortized update time by more than a constant factor.The implementation avoids relying on dynamic hash tables because the paper seeks a fully deterministic algorithm.Source: §5 · pp. 12–13
- Setting the arboricity bound to c = 2√m and rebuilding the orientation when m changes by a factor of 2 yields the arbitrary-graph bound.The maximum allowed out-degree is Δ = 5c, and the paper bounds it by 20√m.Source: §5 · pp. 11, 13
- Amortized O(√m) update time suffices to maintain a maximal matching in arbitrary graphs using O(n + m) space.The theorem assumes the empty graph on n vertices as the starting state.Source: §5 · pp. 11, 13