A fast network-decomposition algorithm and its applications to constant-time distributed computation

A partition (C-1, C-2, . . . ,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 l-colorable is called a strong (resp., weak) (d, l)-network-decomposition. Network-decompositions were introduced in a seminal paper by Awerbuch, Goldberg, Luby and Plotkin in 1989. Awerbuch et al. showed that strong (d, l)-network-decompositions with d = l = exp {O(root logn log logn)} can be computed in distributed deterministic time O(d). Even more importantly, they demonstrated that network-decompositions can be used for a great variety of applications in the message-passing model of distributed computing. The result of Awerbuch et al. was improved by Panconesi and Srinivasan in 1992: in the latter result d = l = exp{O(root logn)}, and the running time is O(d) as well. In another remarkable breakthrough Linial and Saks (in 1992) showed that weak (O(logn), O(logn))-network-decompositions can be computed in distributed randomized time O(log(2)n). Much more recently Barenboim (2012) devised a distributed randomized constant-time algorithm for computing strong network decompositions with d = O(1). However, the parameter l in his result is O (n(1/2+epsilon)). 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(epsilon))-approximation algorithm for the distributed minimum coloring problem, improving the previously bestknown O(n(1/2+epsilon)) 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). (C) 2016 Elsevier B.V. All rights reserved.