Abstract We describe a simple deterministic $$O( \varepsilon ^{-1} \log \Delta )$$ O ( ε - 1 log Δ ) round distributed algorithm for $$(2\alpha +1)(1 + \varepsilon )$$ ( 2 α + 1 ) ( 1 + ε ) approximation of minimum weighted dominating set on graphs with arboricity at most $$\alpha $$ α . Here $$\Delta $$ Δ 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 et al. in JACM 63:116, 2016). Our algorithm improves on all the previous results (that work only for unweighted graphs) including a randomized $$O(\alpha ^2)$$ O ( α 2 ) approximation in $$O(\log n)$$ O ( log n ) rounds (Lenzen et al. in International symposium on distributed computing, Springer, 2010), a deterministic $$O(\alpha \log \Delta )$$ O ( α log Δ ) approximation in $$O(\log \Delta )$$ O ( log Δ ) rounds (Lenzen et al. in international symposium on distributed computing, Springer, 2010), a deterministic $$O(\alpha )$$ O ( α ) approximation in $$O(\log ^2 \Delta )$$ O ( log 2 Δ ) rounds (implicit in Bansal et al. in Inform Process Lett 122:21–24, 2017; Proceeding 17th symposium on discrete algorithms (SODA), 2006), and a randomized $$O(\alpha )$$ O ( α ) approximation in $$O(\alpha \log n)$$ O ( α log n ) rounds (Morgan et al. in 35th International symposiumon distributed computing, 2021). We also provide a randomized $$O(\alpha \log \Delta )$$ O ( α log Δ ) round distributed algorithm that sharpens the approximation factor to $$\alpha (1+o(1))$$ α ( 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 $$\alpha - 1 - \varepsilon $$ α - 1 - ε approximation (Bansal et al. in Inform Process Lett 122:21-24, 2017).

This paper presents significantly improved deterministic algorithms for some of the key problems in the area of distributed graph algorithms, including network decomposition, hitting sets, and spanners. As the main ingredient in these results, we develop novel randomized distributed algorithms that we can analyze using only pairwise independence, and we can thus derandomize efficiently. As our most prominent end-result, we obtain a deterministic construction for O(log n)-color O(log n · log log log n)- strong diameter network decomposition in Õ(log3 n) rounds. This is the first construction that achieves almost log n in both parameters, and it improves on a recent line of exciting progress on deterministic distributed network decompositions [Rozhoň, Ghaffari STOC'20; Ghaffari, Grunau, Rozhoň SODA'21; Chang, Ghaffari PODC'21; Elkin, Haeupler, Rozhoň, Grunau FOCS'22].

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].

This paper presents efficient distributed algorithms for a number of fundamental problems in the area of graph sparsification:We provide the first deterministic distributed algorithm that computes an ultra-sparse spanner in polylog(n) rounds in weighted graphs. Concretely, our algorithm outputs a spanning subgraph with only n + o (n) edges in which the pairwise distances are stretched by a factor of at most O(logn · 2O(log* n) ).