论文标题
最大匹配大小的动态算法
Dynamic Algorithms for Maximum Matching Size
论文作者
论文摘要
我们研究完全动态算法以最大程度的匹配。这是一个充分研究的问题，众所周知可以承认几个更新的时间/近似权衡。例如，已知如何在$ \ log^{o（1）} n $更新时间或$ 2/3 $ -Approximate匹配中维持1/2的匹配匹配，以$ O（\ sqrt {n}）$更新时间，其中$ n $ n $是pertices的数量。确定是否可以改善这些界限中的任何一个是一个长期的开放问题。 在本文中，我们表明，当目标仅维持匹配的大小（而不是其边缘集）时，确实可以改善这些界限。首先，我们提供了一种算法，该算法采用$ \ log^{o（1）} n $更新时间，并维护$ .501 $ -AppRoximation（如果该图为二优胜者，则$ .585 $ -AppRoximation）。其次，我们给出了一种算法，该算法在$ O（\ sqrt {n}）中维持$（2/3 +ω（1））$ - 近似值，用于两部分图。 我们的结果建立在与均匀时间算法的新连接基础上。特别是，两者的关键工具是作者的算法，用于估计$ \ widetilde {o}（n）$ time [behnezhad;焦点2021]。我们的第二个结果也建立在Bernstein和Stein [icalp'15，Soda'16]的边缘限制子图（EDC）上。特别是，虽然已经知道EDC可能不包含大于2/3的approximation，但我们对这种紧密实例进行了新的表征，使我们能够打破它。我们认为，这种特征可能具有独立的利益。
We study fully dynamic algorithms for maximum matching. This is a well-studied problem, known to admit several update-time/approximation trade-offs. For instance, it is known how to maintain a 1/2-approximate matching in $\log^{O(1)} n$ update time or a $2/3$-approximate matching in $O(\sqrt{n})$ update time, where $n$ is the number of vertices. It has been a long-standing open problem to determine whether either of these bounds can be improved. In this paper, we show that when the goal is to maintain just the size of the matching (and not its edge-set), then these bounds can indeed be improved. First, we give an algorithm that takes $\log^{O(1)} n$ update-time and maintains a $.501$-approximation ($.585$-approximation if the graph is bipartite). Second, we give an algorithm that maintains a $(2/3 + Ω(1))$-approximation in $O(\sqrt{n})$ time for bipartite graphs. Our results build on new connections to sublinear time algorithms. In particular, a key tool for both is an algorithm of the author for estimating the size of maximal matchings in $\widetilde{O}(n)$ time [Behnezhad; FOCS 2021]. Our second result also builds on the edge-degree constrained subgraph (EDCS) of Bernstein and Stein [ICALP'15, SODA'16]. In particular, while it has been known that EDCS may not include a better than 2/3-approximation, we give a new characterization of such tight instances which allows us to break it. We believe this characterization might be of independent interest.
