A Fast Network-Decomposition Algorithm and its Applications to Constant-Time Distributed Computation

A partition $(C_1,C_2,\mathrm{.}\mathrm{.}\mathrm{.},C_q)$ of $G=(V,E)$ into clusters of strong (respectively, weak) diameter $d$, such that the supergraph obtained by contracting each $C_i$ is $\mathrm{\ell }$-colorable is called a strong (resp., weak) $(d,\mathrm{\ell })$-network-decomposition. Network-decompositions were introduced in a seminal paper by Awerbuch, Goldberg, Luby and Plotkin in 1989. Awerbuch et al. showed that strong $(exp{O(\sqrt{ \log n \log \log n})}, exp{O(\sqrt{ \log n \log \log n})})$-network-decompositions can be computed in distributed deterministic time $exp\{O(\sqrt{\log n\log \log n})\}$. The result of Awerbuch et al. was improved by Panconesi and Srinivasan in 1992: in the latter result $d=\mathrm{\ell }=exp\{O(\sqrt{\log n})\}$, and the running time is $exp\{O(\sqrt{\log n})\}$ as well. Much more recently Barenboim (2012) devised a distributed randomized constant-time algorithm for computing strong network decompositions with $d=O(1)$. However, the parameter $\mathrm{\ell }$ in his result is $O(n^{1\mathrm{/}2+ϵ})$. In this paper we drastically improve the result of Barenboim and devise a distributed randomized constant-time algorithm for computing strong $(O(1), O(n^{\epsilon}))$-network-decompositions. As a corollary we derive a constant-time randomized $O(n^{ϵ})$-approximation algorithm for the distributed minimum coloring problem, improving the previously best-known $O(n^{1\mathrm{/}2+ϵ})$ approximation guarantee. We also derive other improved distributed algorithms for a variety of problems. Most notably, for the extremely well-studied distributed minimum dominating set problem currently there is no known deterministic polylogarithmic-time algorithm. We devise a {deterministic} polylogarithmic-time approximation algorithm for this problem, addressing an open problem of Lenzen and Wattenhofer (2010).