Near-Optimal Distributed Dominating Set in Bounded Arboricity Graphs
Michal Dory, Mohsen Ghaffari, Saeed Ilchi · 2022
We describe a simple deterministic O(ε-1 log Δ) 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].