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
2398784061 103874125 1997707549 2114986147 2052811387 2092349993
Fundamental local symmetry breaking problems such as Maximal Independent Set (MIS) and coloring have been recognized as important by the community, and studied extensively in (standard) graphs. In particular, fast (i.e., logarithmic run time) randomized algorithms are well-established for MIS and Δ + 1-coloring in both the LOCAL and CONGEST distributed computing models. On the other hand, comparatively much less is known on the complexity of distributed symmetry breaking in hypergraphs. In particular, a key question is whether a fast (randomized) algorithm for MIS exists for hypergraphs. We present a novel distributed algorithm for the maximal independent set (MIS) problem. On growth-bounded graphs (GBG) our deterministic algorithm finishes in O(log* n) time, n being the number of nodes. In light of Linial's Ω(log* n) lower bound our algorithm is asymptotically optimal. Our algorithm answers prominent open problems in the ad hoc sensor network domain. For instance, it solves the connected dominating set problem for unit disk graphs in O(log* n) time, exponentially faster than the state-of-the-art algorithm. With a new extension our algorithm also computes a delta+1 coloring in O(log* n) time, where delta is the maximum degree of the graph. Many large-scale networks such as ad hoc and sensor networks, peer-to-peer networks, or the Internet have the property that the number of independent nodes does not grow arbitrarily when looking at neighborhoods of increasing size. Due to this bounded "volume growth," one could expect that distributed algorithms are able to solve many problems more efficiently than on general graphs. The goal of this paper is to help understanding the distributed complexity of problems on "bounded growth" graphs. We show that on the widely used unit disk graph, covering and packing linear programs can be approximated by constant factors in constant time. For a more general network model which is based on the assumption that nodes are in a metric space of constant doubling dimension, we show that in O(log*!n) rounds it is possible to construct a (O(1), O(1))-network decomposition. This results in asymptotically optimal O(log*!n) time algorithms for many important problems. The efficient distributed construction of a maximal independent set (MIS) of a graph is of fundamental importance. We study the problem in the class of Growth-Bounded Graphs, which includes for example the well-known Unit Disk Graphs. In contrast to the fastest (time-optimal) existing approach [11], we assume that no geometric information (e.g., distances in the graph's embedding) is given. Instead, nodes employ randomization for their decisions. Our algorithm computes a MIS in O(log log n • log* n) rounds with very high probability for graphs with bounded growth, where n denotes the number of nodes in the graph. In view of Linial's Ω(log* n) lower bound for computing a MIS in ring networks [12], which was extended to randomized algorithms independently by Naor [18] and Linial [13], our solution is close to optimal. In a nutshell, our algorithm shows that for computing a MIS, randomization is a viable alternative to distance information. 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.