Distributed Dominating Set With Optimal Rounds and Message Size in Bounded Arboricity Graphs (opens in new tab)

We study the distributed minimum dominating set problem on graphs of arboricity $\alpha$. Dory, Ghaffari, and Ilchi [PODC'22] showed that any algorithm achieving a constant or poly-logarithmic approximation factor needs at least $\Omega(\log\Delta/\log\log\Delta)$ rounds in graphs of maximum degree $\Delta$ and arboricity $\alpha$, even when $\alpha=2$ and even when the message sizes are unbounded. Although there is a variety of algorithms with ...