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 ℓ-colorable is called a strong (resp. , weak) ( d, ℓ ) -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, ℓ ) -network-decompositions with d = ℓ = exp ⁡ { O ( log ⁡ n log ⁡ log ⁡ n ) } 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 = ℓ = exp ⁡ { O ( log ⁡ n ) }, and the running time is O ( d ) as well. In another remarkable breakthrough Linial and Saks (in 1992) showed that weak ( O ( log ⁡ n ), O ( log ⁡ n ) ) -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 ℓ in his result is O ( n 1 / 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 ϵ ) ) -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 / 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).

Authors

• Leonid Barenboim
• Michael Elkin
• Cyril Gavoille

Keywords

• Distributed algorithms
• Local algorithms
• Dominating sets
• Coloring
• Spanners