Dynamic (1 + ∊)-Approximate Matchings: A Density-Sensitive Approach
Dynamic (1 + ∊)-Approximate Matchings: A Density-Sensitive Approach
复制标题
动态 (1 + ∊)-近似匹配：密度敏感方法
DOI：
10.1137/1.9781611974331.ch51
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Shay Solomon
中科院分区：
文献类型：
--
作者：
D. Peleg;Shay Solomon
近几年来，全动态图的近似匹配问题得到了广泛的研究。Cupta和Peng[FOCS‘13]给出了对任意e>；0，m表示图中当前边的个数的最坏情况更新时间为O([公式])的一般图的全动态(1+e)-近似最大基数匹配(MCM)的确定性算法。尽管做了大量的研究工作，但即使允许分期计时和随机化，或者允许近似因子从1+e增加到2-e，甚至在基本图族(如平面图)中，这种[方程]更新时间障碍仍然是最先进的。本文提出了一个简单的确定性算法，其性能依赖于图的密度。具体地说，对于图的边度1有界于α的图，我们保持最坏情况更新时间为O(α·e-2)的完全动态(1+e)-近似矩阵矩阵。即使树度界限α动态改变，更新时间界限也保持不变。由于簇度介于1和[方程]之间，我们的密度敏感界O(α·e-2)自然地推广了Gupta和Peng的O([方程]·e-2)界。对于有界树度图族(包括森林图、平面图和不含固定子式的图)，在e=O(1)的情形下，我们的更新时间减少到一个常数。这应该与以前关于有界树形图的最佳2-逼近结果形成对比，后者要么达到O(Logn)最坏情况界(Kopelowitz等人，ICALP‘14)，要么达到O([等式])摊销界(他等人，Isaac’14)，其中n表示图中的顶点数。在此过程中，我们提供了独立感兴趣的局部算法来保持完全动态的近似匹配和顶点覆盖。
Approximate matchings in fully dynamic graphs have been intensively studied in recent years. Cupta and Peng [FOCS'13] presented a deterministic algorithm for maintaining fully dynamic (1 + e)-approximate maximum cardinality matching (MCM) in general graphs with worst-case update time O([EQUATION]), for any e > 0, where m denotes the current number of edges in the graph. Despite significant research efforts, this [EQUATION] update time barrier remains the state-of-the-art even if amortized time bounds and randomization are allowed or the approximation factor is allowed to increase from 1 + e to 2 -- e, and even in basic graph families such as planar graphs. This paper presents a simple deterministic algorithm whose performance depends on the density of the graph. Specifically, we maintain fully dynamic (1 + e)-approximate MCM with worst-case update time O(α ·e--2) for graphs with arboricity1 bounded by α. The update time bound holds even if the arboricity bound α changes dynamically. Since the arboricity ranges between 1 and [EQUATION], our density-sensitive bound O(α · e--2) naturally generalizes the O([EQUATION] · e--2) bound of Gupta and Peng. For the family of bounded arboricity graphs (which includes forests, planar graphs, and graphs excluding a fixed minor), in the regime e = O(1) our update time reduces to a constant. This should be contrasted with the previous best 2-approximation results for bounded arboricity graphs, which achieve either an O(log n) worst-case bound (Kopelowitz et al., ICALP'14) or an O([EQUATION]) amortized bound (He et al., ISAAC'14), where n stands for the number of vertices in the graph. En route to this result, we provide local algorithms of independent interest for maintaining fully dynamic approximate matching and vertex cover.