2009/05/31 by Leonid Barenboim, Michael Elkin · 3 citations
Computer Science · #Complexity and Algorithms in Graphs #Optimization and Search Problems #Cryptography and Data Security #Computer science
paper · doi:10.1145/1536414.1536432
openalex publication_date 2009/05/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
The distributed ( ∆ + 1)-coloring problem is one of most fundamental and well-studied problems of Distributed Algorithms. Starting with the work of Cole and Vishkin in 86, there was a long line of gradually improving algorithms published. The current state-of-the-art running time is O(∆log ∆ + log ∗ n), due to Kuhn and Wattenhofer, PODC’06. Linial (FOCS’87) has proved a lower bound of 1 2 log ∗ n for the problem, and Szegedy and Vishwanathan (STOC’93) provided a heuristic argument that shows that algorithms from a wide family of locally iterative algorithms are unlikely to achieve running time smaller than Θ(∆log ∆). We present a deterministic (∆+1)-coloring distributed algorithm with running time O(∆)+ 1 2 log ∗ n. We also present a tradeoff between the running time and the number of colors, and devise an O( ∆ 1+ǫ)-coloring algorithm with running time O( ∆ 1−ǫ +log ∗ n), for any constant ǫ, 0 < ǫ ≤ 1/4. Our algorithm breaks the heuristic barrier of Szegedy and Vishwanathan, and achieves running time which is linear in the maximum degree ∆. On the other hand, the conjecture of Szegedy and Vishwanathan may still be true, as our algorithm is not from the family of locally iterative algorithms. On the way to this result we introduce a generalization of the notion of graph coloring, which we call relaxed coloring. In an m-relaxed p-coloring the vertices are colored with p colors so that each vertex has up to m neighbors with the same color. We show that an m-relaxed p-coloring with reasonably small m and p can be computed very efficiently. We also develop a technique to employ multiple relaxed colorings of various subgraphs of the original graph G for computing a ( ∆ + 1)-coloring of G. We believe that these techniques and the notion of relaxed coloring are of independent interest.