TY - JOUR

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

AU - Barenboim, Leonid

AU - Elkin, Michael

AU - Gavoille, Cyril

N1 - Publisher Copyright:
© 2016 Elsevier B.V.

PY - 2018/12/3

Y1 - 2018/12/3

N2 - A partition (C1,C2,…,Cq) of G=(V,E) into clusters of strong (respectively, weak) diameter d, such that the supergraph obtained by contracting each Ci 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(lognloglogn)} 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(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(log2n). 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(n1/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(n1/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).

AB - A partition (C1,C2,…,Cq) of G=(V,E) into clusters of strong (respectively, weak) diameter d, such that the supergraph obtained by contracting each Ci 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(lognloglogn)} 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(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(log2n). 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(n1/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(n1/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).

KW - Coloring

KW - Distributed algorithms

KW - Dominating sets

KW - Local algorithms

KW - Spanners

UR - http://www.scopus.com/inward/record.url?scp=85032330994&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2016.07.005

DO - 10.1016/j.tcs.2016.07.005

M3 - ???researchoutput.researchoutputtypes.contributiontojournal.article???

AN - SCOPUS:85032330994

SN - 0304-3975

VL - 751

SP - 2

EP - 23

JO - Theoretical Computer Science

JF - Theoretical Computer Science

ER -