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

$(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})\}$

. 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. 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. This improves the best previously-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).