The @math -coloring problem is a fundamental symmetry breaking problem in distributed computing. We give a new randomized coloring algorithm for @math -coloring running in @math rounds with probability @math in a graph with @math nodes and maximum degree @math . This implies that the @math -coloring problem is easier than the maximal independent set problem and the maximal matching problem, due to their lower bounds by Kuhn, Moscibroda, and Wattenhofer [PODC'04]. Our algorithm also extends to the list-coloring problem where the palette of each node contains @math colors.
@cite_24 investigated distributed coloring where the number of colors used depends on the chromatic number @math . Their algorithm requires @math colors and running time of @math for graphs with @math and @math .
@cite_24
2119761906
We introduce Multi-Trials, a new technique for symmetry breaking for distributed algorithms and apply it to various problems in general graphs. For instance, we present three randomized algorithms for distributed (vertex or edge) coloring improving on previous algorithms and showing a time color trade-off. To get a Δ+1 coloring takes time O(log Δ+ √ log n). To obtain an O(Δ+log1+1 log*nn) coloring takes time O(log* n). This is more than an exponential improvement in time for graphs of polylogarithmic degree. Our fastest algorithm works in constant time using O(Δlog(c) n+ log1+1 c n) colors, where c denotes an arbitrary constant and log(c ) n denotes the c times (recursively) applied logarithm ton. We also use the Multi-Trials technique to compute network decompositions and to compute maximal independent set (MIS), obtaining new results for several graph classes.