Near-Optimal Distributed Dominating Set in Bounded Arboricity Graphs
share
We describe a simple deterministic O( ε^-1logΔ) round distributed algorithm for (2α+1)(1 + ε) 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 - ε approximation [Bansal and Umboh IPL'17].
READ FULL TEXT