On the complexity of distributed network decomposition

In this paper, we improve the bounds for computing a network decomposition distributively and deterministically. Our algorithm computes an (n(epsilon(n)), n(epsilon(n)))-decomposition in n(O(epsilon(n))) time, where epsilon(n) = 1/root log n. As a corollary we obtain improved deterministic bounds for distributively computing several graph structures such as maximal independent sets and Delta-vertrx colorings. We also show that the class of graphs G whose maximum degree is n(O(delta(n))) where delta(n) = 1/log log n is complete for the task of computing a near-optimal decomposition, i.e., a (log n,log n)-decomposition, in polylog(n) time. This is a corollary of a more general characterization, which pinpoints the weak points of existing network decomposition algorithms. Completeness is to be intended in the following sense: if we have an algorithm A that computes a near-optimal decomposition in polylog(n) time for graphs in G, then we can compute a near-optimal decomposition in polylog(n) time for all graphs. (C) 1996 Academic Press, Inc.