Fully Dynamic Matching: Beating 2-Approximation in Δ Update Time.ϵ

Soheil Behnezhad, Jakub Lacki, Vahab S. MirrokniSODA 2019 · DOI · OpenReview

TL;DR

This paper presents a new randomized algorithm for maintaining a near-optimal matching in a graph that is constantly changing (fully dynamic). It achieves a better-than-2 approximation of the maximum matching with an update time of O(Δϵ + polylog n), significantly improving upon previous algorithms. This work addresses a long-standing open question in the field of dynamic graph algorithms.

What Problem Does This Paper Address?

Maintaining a maximum matching in a graph is a fundamental problem in computer science. In a static graph, algorithms can find a maximum matching efficiently. However, in dynamic graphs, edges are constantly being added or removed, making it challenging to keep the matching updated.

Existing algorithms can maintain a 2-approximation of the maximum matching (meaning the matching found is at least half the size of the true maximum) very quickly, in polylogarithmic time per update. This is great for a basic guarantee. However, the question of how to achieve a better-than-2 approximation (e.g., a 1.5-approximation) with fast update times has been a major open problem for over a decade. Previous algorithms that offered better approximations were significantly slower, with update times of O(m¹/⁴) or even O(n) in restricted cases. This paper tackles this gap, aiming to provide a better approximation than 2 with a more efficient update time.

Methods

The core of the paper's contribution lies in a novel randomized algorithm that builds upon existing techniques for maintaining matchings. Here's a breakdown of their approach:

  • Random Greedy Maximal Matching (RGMM): The algorithm starts by computing a random greedy maximal matching, denoted as $M_0$. This is a standard technique where edges are processed in a random order, and an edge is added to the matching if it doesn't conflict with already chosen edges. The paper leverages recent work showing that RGMM can be maintained efficiently in dynamic settings.
  • Partitioning and Augmenting: To break the 2-approximation barrier, the algorithm partitions the edges of $M_0$ into $1/\epsilon$ sets based on their ranks. For each partition, it constructs auxiliary graphs and uses RGMM again to find augmenting paths. The key idea is that if $M_0$ is not "too large" compared to the optimal matching, then most of its edges can be part of "length-3 augmenting paths" that can improve the matching.
  • Parametrized Analysis: A crucial technical innovation is a parametrized analysis of the update time. Instead of a single update time, they analyze it based on the distribution of edge ranks within $M_0$. This allows them to bound the update time by $\tilde{O}(\rho)$, where $\rho$ is related to the maximum rank ratio within partitions.
  • Handling Vertex Updates: A significant challenge in dynamic graph algorithms is efficiently handling vertex insertions/deletions, which can cascade through the algorithm. The paper introduces a careful procedure to manage these changes by focusing on vertices whose matching status in $M_0$ has changed.
  • Black-Box Tools: The algorithm relies on two key existing results:
  • A deterministic algorithm for maintaining a $(1+\epsilon)$-approximate matching with $O(\Delta'/\epsilon^2)$ update time, where $\Delta'$ is the maximum degree.
  • An efficient dynamic RGMM maintenance algorithm with expected polylogarithmic update time.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • The "Dense Region" Problem: The paper highlights why simple greedy algorithms (like RGMM) struggle to break the 2-approximation. They tend to match edges in "dense regions" of the graph, which can be suboptimal if a perfect matching exists elsewhere.
  • Length-3 Augmenting Paths are Key: The core idea to improve beyond 2-approximation is to find "length-3 augmenting paths." These are paths of the form $u-v-w-x$ where $u-v$ and $w-x$ are edges in the current matching, and $v-w$ is an edge not in the matching. Finding such paths allows for a significant improvement in matching size.
  • Randomization as a Defense: The use of randomization is crucial. By randomizing edge ranks and vertex partitions, the algorithm makes it difficult for an adversary (who knows the algorithm but not the random bits) to consistently disrupt the matching process.
  • Adaptive Graph Construction: The algorithm's efficiency hinges on its ability to adaptively construct auxiliary graphs ($G_i$) based on the current state of the matching $M_0$. This is a common theme in dynamic graph algorithms but presents significant implementation challenges.
  • Bridging Static and Dynamic: The paper effectively bridges insights from static approximate matching algorithms with the demands of dynamic graph maintenance, showing how to adapt powerful static techniques to a constantly changing environment.

Key Results

The paper's main result is a randomized algorithm for fully dynamic general graphs that maintains a $(2 - \Omega(\epsilon))$ approximate maximum matching with a worst-case update time of $O(\Delta\epsilon + \text{polylog } n)$, where $\Delta$ is the maximum degree and $\epsilon$ is a constant. This is a significant improvement over previous algorithms, which offered either a 2-approximation with polylogarithmic time or a better approximation with much slower update times.

Limitations and Future Work

  • Randomized Algorithm: The algorithm is randomized, meaning its performance is guaranteed with high probability. While this is common in theoretical computer science, deterministic algorithms are often preferred in practice if achievable with similar efficiency.
  • Worst-Case Update Time: While the paper claims a worst-case update time, the underlying analysis relies on expected time for some components. The reduction to worst-case is mentioned but not detailed in the provided text.
  • Constant $\epsilon$: The approximation factor is $2 - \Omega(\epsilon)$, meaning it's a constant factor improvement over 2. Achieving a constant approximation factor that is independent of $\epsilon$ (e.g., a fixed 1.5-approximation) with similar update times remains an open challenge.
  • Future Work: The paper suggests that further work could explore deterministic versions of their algorithm or investigate if even faster update times are possible for better approximations. The authors also hint at potential applications of their techniques to other dynamic graph problems.

Summary updated

Abstract

In fully dynamic graphs, we know how to maintain a 2-approximation of maximum matching extremely fast, that is, in polylogarithmic update time or better. In a sharp contrast and despite extensive studies, all known algorithms that maintain a 2 – Ω(1) approximate matching are much slower. Understanding this gap and, in particular, determining the best possible update time for algorithms providing a better-than-2 approximate matching is a major open question. In this paper, we show that for any constant ϵ > 0, there is a randomized algorithm that with high probability maintains a 2 – Ω(1) approximate maximum matching of a fully-dynamic general graph in worst-case update time O(Δϵ + polylog n), where Δ is the maximum degree. Previously, the fastest fully dynamic matching algorithm providing a better-than-2 approximation had O(m1/4) update-time [Bernstein and Stein, SODA 2016]. A faster algorithm with update-time O(nϵ) was known, but worked only for maintaining the size (and not the edges) of the matching in bipartite graphs [Bhattacharya, Henzinger, and Nanongkai, STOC 2016].
BibTeX
@inproceedings{behnezhad2019fully,
  author = {Soheil Behnezhad and Jakub Lacki and Vahab S. Mirrokni},
  title = {{Fully Dynamic Matching: Beating 2-Approximation in Δ Update Time.ϵ}},
  booktitle = {SODA},
  year = {2019},
  doi = {10.1137/1.9781611975994.152},
}
Figure