论文标题
交通拥堵模型中的近似二分顶点盖
Approximate Bipartite Vertex Cover in the CONGEST Model
论文作者
论文摘要
我们为交通拥堵模型中的两部分图中的最小顶点覆盖问题提供了有效的分布式算法。从kőnig的定理来看，众所周知，在两部分图中，最小顶点盖的大小等于最大匹配的大小。我们首先证明，与现有的$ O（N \ log n）$ - 圆形算法一起计算最大匹配，Kőnig定理的建设性证明直接导致确定性$ O（N \ log n）$ - 圆形的圆形圆形杂货算法计算最小顶点封面。然后，我们证明，通过调整构造，我们还可以将\ emph {近似}的最大匹配转换为\ emph {近似}最小顶点盖。给定某些$δ> 1 $的$（1-δ）$ - 近似匹配，我们表明可以在时间$ o（d+\ mathrm {poly}（\ frac {\ frac {\ log n}Δ）$中计算出$（1+o（δ））$ - 近似顶点封面。与已知的图形聚类技术结合时，对于任何$ \ varepsilon \ in（0,1] $，这将导致$ \ m atrm {poly}（\ frac {\ frac {\ log n} {\ varepsilon} {\ varepsilon}）$ - 时间确定性，以及稍微确定的，稍微更快的$ o（\ frac） n} {\ varepsilon^3}）$ - 用于计算$（1+ \ varepsilon）$的圆形拥塞算法 - 在两部分图中的近似顶点覆盖率，用于常数$ \ varepsilon $，随机时间复杂度与$ω（\ log n）$ compers a $ comperte comperte usecte（\ log n）即使在本地模型中，两分也与一般图中的情况形成鲜明对比，众所周知，计算最佳顶点覆盖物需要$ \tildeΩ（n^2）$ roughs $ \ tildex（n^2）$。
We give efficient distributed algorithms for the minimum vertex cover problem in bipartite graphs in the CONGEST model. From Kőnig's theorem, it is well known that in bipartite graphs the size of a minimum vertex cover is equal to the size of a maximum matching. We first show that together with an existing $O(n\log n)$-round algorithm for computing a maximum matching, the constructive proof of Kőnig's theorem directly leads to a deterministic $O(n\log n)$-round CONGEST algorithm for computing a minimum vertex cover. We then show that by adapting the construction, we can also convert an \emph{approximate} maximum matching into an \emph{approximate} minimum vertex cover. Given a $(1-δ)$-approximate matching for some $δ>1$, we show that a $(1+O(δ))$-approximate vertex cover can be computed in time $O(D+\mathrm{poly}(\frac{\log n}δ))$, where $D$ is the diameter of the graph. When combining with known graph clustering techniques, for any $\varepsilon\in(0,1]$, this leads to a $\mathrm{poly}(\frac{\log n}{\varepsilon})$-time deterministic and also to a slightly faster and simpler randomized $O(\frac{\log n}{\varepsilon^3})$-round CONGEST algorithm for computing a $(1+\varepsilon)$-approximate vertex cover in bipartite graphs. For constant $\varepsilon$, the randomized time complexity matches the $Ω(\log n)$ lower bound for computing a $(1+\varepsilon)$-approximate vertex cover in bipartite graphs even in the LOCAL model. Our results are also in contrast to the situation in general graphs, where it is known that computing an optimal vertex cover requires $\tildeΩ(n^2)$ rounds in the CONGEST model and where it is not even known how to compute any $(2-\varepsilon)$-approximation in time $o(n^2)$.
