For a pair of positive parameters @math , a partition @math of the vertex set @math of an @math -vertex graph @math into disjoint clusters of diameter at most @math each is called a @math network decomposition, if the supergraph @math , obtained by contracting each of the clusters of @math , can be properly @math -colored. The decomposition @math is said to be strong (resp., weak) if each of the clusters has strong (resp., weak) diameter at most @math , i.e., if for every cluster @math and every two vertices @math , the distance between them in the induced graph @math of @math (resp., in @math ) is at most @math . Network decomposition is a powerful construct, very useful in distributed computing and beyond. It was shown by Awerbuch al AGLP89 and Panconesi and Srinivasan PS92 , that strong @math network decompositions can be computed in @math distributed time. Linial and Saks LS93 devised an ingenious randomized algorithm that constructs weak @math network decompositions in @math time. It was however open till now if strong network decompositions with both parameters @math can be constructed in distributed @math time. In this paper we answer this long-standing open question in the affirmative, and show that strong @math network decompositions can be computed in @math time. 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 al BGKMPT11 , and Miller al MPX13 . These authors developed this approach for PRAM algorithms for padded partitions. We adapt their approach to network decompositions in the distributed model of computation.
Barenboim al @cite_14 devised a randomized constant time algorithm for constructing strong @math network decompositions, for an arbitrarily small constant @math . Kutten al @cite_1 extended the algorithm of Linial and Saks @cite_11 for constructing network decompositions to hypergraphs. A long line of research developed network decompositions for graphs of bounded growth, see, e.g., @cite_13 @cite_5 @cite_2 .
@cite_14 @cite_1 @cite_2 @cite_5 @cite_13 @cite_11
2487418934 2503706701 1996066664 2092349993
Abstract 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. showed that strong ( d , l ) -network-decompositions with d = l = 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 was improved by Panconesi and Srinivasan in 1992: in the latter result d = l = 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 l 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). We show that the first phase of the Linial-Saks network decomposition algorithm gives a randomized distributed O(ne)-approximation algorithm for the maximum independent set problem that operates in O(1 e) rounds, and we give a matching lower bound that holds even for bipartite graphs. The authors introduce a concept of network decomposition, a partitioning of an arbitrary graph into small-diameter connected components, such that the graph created by contracting each component into a single node has low chromatic number. They present an efficient distributed algorithm for constructing such a decomposition and demonstrate its use for design of efficient distributed algorithms. The method yields new deterministic distributed algorithms for finding a maximal independent set in an arbitrary graph and for ( Delta +1)-coloring of graphs with maximum degree Delta . These algorithms run in O(n sup epsilon ) time for epsilon =O((log log n log n) sup 1 2 ), whereas the best previously known deterministic algorithms required Omega (n) time. The techniques can also be used to remove randomness from the previously known most distributed breadth-first search algorithm. > Chapter 36 Decomposing Graphs into Regions of Small Diameter* Nathan Linialt Michael .lss A decomposition of a graph G = (V, E) is a partition of the vertex set into subsets (called lhks). The diameter of a decomposition is the least. d such that any two vertices belonging to the same connected component of a block are at distance < d. In this paper we prove (nearly best possible) statements of the form: .4ny n–vertex graph has a decomposition into a small number of blocks each having small diameter. Such decompositions provide a tool for efficiently decentralizing distributed computations. In [AGLP1 it was shown that every graph has a decomposition into at most s(n) blocks of diameter at most s(n) for s(n) = o( loglog d h n). usinga,technique of Awerbuch [A] and Awerbuch and Peleg [AP], we improve this result by showing that every graph has a decomposition of diameter ()(log n) into O(log n) blocks. In addition, we give a randomized distributed algorithm that produces such a decomposition and runs in time 0(log2 n). The construction can be parametrized to provide decompositions that trade-off between the number of blocks and the diameter. We show that this trade-off is nearly best possible for two families of graphs the first consists of skeletons of certain triangulations of a simplex and the second consists of grid graphs with added diagonals. The proofs in both cases rely on basic results in combinatorial topology, Sperner’s lemma for the first class and Tucker’s lemma for the second. *This work was supported in part by NSF contracts DMS87-03541 and CCR-8911388 tDepartment of Computer Science, Hebrew University, Jerusalem, Israel. + ‘Department of Computer Science and Engineering, Mail Code C-014, University of California, San Diego, La Jolla, CA 92093-0114.