论文标题
在有界的支撑图中，近乎最佳的分布式统治集
Near-Optimal Distributed Dominating Set in Bounded Arboricity Graphs
论文作者
论文摘要
我们描述了一个简单的确定性$ O（\ varepsilon^{ - 1} \logδ）$ round分布式算法，$（2α + 1）（1 + \ varepsilon）$最小加权支配集合的最小加权主导设置的近似值最多具有$α$。 $Δ$在这里表示最高学位。我们还显示了下限证明，即使对于未加权的情况，这种圆形的复杂性也几乎是最佳的，这是通过从分布式顶点覆盖近似的著名KMW下限的降低[Kuhn，Moscibroda和Wattenhofer Jacm'16]。 我们的算法改进了所有先前的结果（仅适用于未加权图），包括$ o（\ log n）$ rounds的随机$ o（α^2）$近似[lenzen和wattenhofer disc'10] DISC'10]，一个确定性的$ O（α）$（$ o（\ log^2δ）$ roughs [隐含在Bansal和Umboh Ipl'17和Kuhn，Moscibroda和Wattenhofer Soda'06]，以及随机化的$ O（α）$ O（α）$ O（α）$ o（log n log n nor）normon nor的$ o（α）$ normon norome normon normon normon normon norome norome norome。 我们还提供了一个随机$ O（α\logδ）$圆形分布式算法，该算法将近似因子缩减为$α（1+o（1））$。如果每个节点仅限于进行多项式时间计算，则我们的近似因子在一阶中很紧，因为实现$α-1- \ varepsilon $近似[Bansal和Umboh IPL'17]是NP-HARD。
We describe a simple deterministic $O( \varepsilon^{-1} \log Δ)$ round distributed algorithm for $(2α+1)(1 + \varepsilon)$ approximation of minimum weighted dominating set on graphs with arboricity at most $α$. Here $Δ$ denotes the maximum degree. We also show a lower bound proving that this round complexity is nearly optimal even for the unweighted case, via a reduction from the celebrated KMW lower bound on distributed vertex cover approximation [Kuhn, Moscibroda, and Wattenhofer JACM'16]. Our algorithm improves on all the previous results (that work only for unweighted graphs) including a randomized $O(α^2)$ approximation in $O(\log n)$ rounds [Lenzen and Wattenhofer DISC'10], a deterministic $O(α\log Δ)$ approximation in $O(\log Δ)$ rounds [Lenzen and Wattenhofer DISC'10], a deterministic $O(α)$ approximation in $O(\log^2 Δ)$ rounds [implicit in Bansal and Umboh IPL'17 and Kuhn, Moscibroda, and Wattenhofer SODA'06], and a randomized $O(α)$ approximation in $O(α\log n)$ rounds [Morgan, Solomon and Wein DISC'21]. We also provide a randomized $O(α\logΔ)$ round distributed algorithm that sharpens the approximation factor to $α(1+o(1))$. If each node is restricted to do polynomial-time computations, our approximation factor is tight in the first order as it is NP-hard to achieve $α- 1 - \varepsilon$ approximation [Bansal and Umboh IPL'17].
