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_0: We present a novel distributed algorithm for the maximal independent set problem (This is an extended journal version of Schneider and Wattenhofer in Twenty-seventh annual ACM SIGACT-SIGOPS symposium on principles of distributed computing, 2008). On bounded-independence graphs 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. Furthermore, 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 δ + 1 coloring and a maximal matching in O(log* n) time, where δ is the maximum degree of the graph.
@cite_44: Graph coloring is a central problem in distributed computing. Both vertex- and edge-coloring problems have been extensively studied in this context. In this paper we show that a (2Δ − 1)-edge-coloring can be computed in time smaller than loge n for any e > 0, specifically, in eO([EQUATION]log log n) rounds. This establishes a separation between the (2Δ − 1)-edge-coloring and Maximal Matching problems, as the latter is known to require Ω([EQUATION]log n) time [15]. No such separation is currently known between the (Δ + 1)-vertex-coloring and Maximal Independent Set problems. We devise a (1 + e)Δ-edge-coloring algorithm for an arbitrarily small constant e > 0. This result applies whenever Δ ≥ Δe, for some constant Δe which depends on e. The running time of this algorithm is O(log* Δ + [EQUATION]). A much earlier logarithmic-time algorithm by Dubhashi, Grable and Panconesi [11] assumed Δ ≥ (log n)1+Ω(1). For Δ = (log n)1+Ω(1) the running time of our algorithm is only O(log* n). This constitutes a drastic improvement of the previous logarithmic bound [11, 9]. Our results for (2Δ − 1)-edge-coloring also follows from our more general results concerning (1 − e)-locally sparse graphs. Specifically, we devise a (Δ + 1)-vertex coloring algorithm for (1 − e)-locally sparse graphs that runs in O(log* Δ + log(1 e)) rounds for any e > 0, provided that eΔ = (log n)1+Ω(1). We conclude that the (Δ + 1)-vertex coloring problem for (1 − e)-locally sparse graphs can be solved in O(log(1 e)) + eO([EQUATION]log log n) time. This imply our result about (2Δ − 1)-edge-coloring, because (2Δ − 1)-edge-coloring reduces to (Δ + 1)-vertex-coloring of the line graph of the original graph, and because line graphs are (1 2 + o(1))-locally sparse.
@cite_51: Symmetry-breaking problems are among the most well studied in the field of distributed computing and yet the most fundamental questions about their complexity remain open. In this article we work in the LOCAL model (where the input graph and underlying distributed network are identical) and study the randomized complexity of four fundamental symmetry-breaking problems on graphs: computing MISs (maximal independent sets), maximal matchings, vertex colorings, and ruling sets. A small sample of our results includes the following: —An MIS algorithm running in O(log2D Δ L 2√log n, and comes close to the Ω(flog Δ log log Δ lower bound of Kuhn, Moscibroda, and Wattenhofer. —A maximal matching algorithm running in O(log Δ + log 4log n) time. This is the first significant improvement to the 1986 algorithm of Israeli and Itai. Moreover, its dependence on Δ is nearly optimal. —A (Δ + 1)-coloring algorithm requiring O(log Δ + 2o(√log log n) time, improving on an O(log Δ + √log n)-time algorithm of Schneider and Wattenhofer. —A method for reducing symmetry-breaking problems in low arboricity degeneracy graphs to low-degree graphs. (Roughly speaking, the arboricity or degeneracy of a graph bounds the density of any subgraph.) Corollaries of this reduction include an O(√log n)-time maximal matching algorithm for graphs with arboricity up to 2√log n and an O(log 2 3n)-time MIS algorithm for graphs with arboricity up to 2(log n)1 3. Each of our algorithms is based on a simple but powerful technique for reducing a randomized symmetry-breaking task to a corresponding deterministic one on a poly(log n)-size graph.
@cite_2: Vertex coloring is a central concept in graph theory and an important symmetry-breaking primitive in distributed computing. Whereas degree-Δ graphs may require palettes of Δ + 1 colors in the worst case, it is well known that the chromatic number of many natural graph classes can be much smaller. In this paper we give new distributed algorithms to find ( Δ k ) -coloring in graphs of girth 4 (triangle-free graphs), girth 5, and trees. The parameter k can be at most ( 1 4 - o ( 1 ) ) ln ? Δ in triangle-free graphs and at most ( 1 - o ( 1 ) ) ln ? Δ in girth-5 graphs and trees, where o ( 1 ) is a function of Δ. Specifically, for Δ sufficiently large we can find such a coloring in O ( k + log * ? n ) time. Moreover, for any Δ we can compute such colorings in roughly logarithmic time for triangle-free and girth-5 graphs, and in O ( log ? Δ + log Δ ? log ? n ) time on trees. As a byproduct, our algorithm shows that the chromatic number of triangle-free graphs is at most ( 4 + o ( 1 ) ) Δ ln ? Δ , which improves on Jamall's recent bound of ( 67 + o ( 1 ) ) Δ ln ? Δ . Finally, we show that ( Δ + 1 ) -coloring for triangle-free graphs can be obtained in sublogarithmic time for any Δ.
More efficient algorithms for @math -coloring exist for very dense graphs, e.g. a deterministic O( @math ) algorithm for growth bounded graphs (e.g. unit disk graphs) @cite_0 , as well as for many types of sparse graphs @cite_51 @cite_44 @cite_2 , e.g. for graphs of low arboricity. @cite_44 described a @math -coloring algorithm for locally-sparse graphs. We will extend this result to cover list-colorings as well.