Improved distributed algorithms for coloring and network decomposition problems
Alessandro Panconesi, Aravind Srinivasan · 1992
This paper deals with the problems of computing a maximal independent set and a vertex coloring in a dktributed model of computation.Given a connected graph G = (V, E) with IVI = n and maximum degree A such that G is neither a complete graph nor an odd cycle, Brooks' theorem shows that G can be colored with A colors.We generalize thk as follows: let G -w be A-colored; then, v can be colored by considering the vertices in an O(loga n) radius around v, and this is tight.Using this, we show that A-coloring G is reducible in 0(log3 n/log A) time to (A+ I)-vertex coloring G in a distributed model.This leads to fast distributed algorithms, and a linear-processor NC algorithm, for Acoloring.We also prove a tight Q(diameter(G)) lower bound for A-edge-coloring bipartite graphs, even with unlimited randomness.When A = 2, this implies an Q(n) lower bound for vertex coloring paths and even cycles.A fundamental notion in distributed graph algorithms is that of a cluster decomposition, introduced by Awerbuch, Goldberg, Luby and Plotkin.We improve the existing bounds by showing how to compute a cluster decomposition in O(n"('(")) ) time, where e(n) = 1/=.This implies improved bounds for several problems, such as computing a maximal independent set and a (A + I )-coloring.We also show how to compute a A-coloring within the same time bound, using our reduction technique.Next, we show that the problem of doing better than O(n"('(m))) time for cluster decomposition is self-reducible to graphs of "intermediate" diameter and degree.This pinpoints the weak points of existing cluster decomposition algorithms.