Distributed strong diameter network decomposition

For a pair of positive parameters , a partition of the vertex set of an -vertex graph into disjoint clusters of diameter at most each is called a , if the supergraph , obtained by contracting each of the clusters of , can be properly -colored. The decomposition is said to be (resp., ) if each of the clusters has strong (resp., weak) diameter at most , i.e., if for every cluster and every two vertices , the distance between them in the induced graph of (resp., in ) is at most .Network decomposition is a powerful construct, very useful in distributed computing and beyond. In this paper we show that strong network decompositions can be computed in time in the CONGEST model. We also present a tradeoff between parameters of our network decomposition. Our work is inspired by and relies on the “shifted shortest path approach”, due to Blelloch et al. , and Miller et al. . These authors developed this approach for PRAM algorithms for padded partitions. We adapt their approach to network decompositions in the distributed model of computation.