Near-Optimal Distributed Degree+1 Coloring
share
We present a new approach to randomized distributed graph coloring that is simpler and more efficient than previous ones. In particular, it allows us to tackle the (deg+1)-list-coloring (D1LC) problem, where each node v of degree d_v is assigned a palette of d_v+1 colors, and the objective is to find a proper coloring using these palettes. While for (Δ+1)-coloring (where Δ is the maximum degree), there is a fast randomized distributed O(log^3log n)-round algorithm (Chang, Li, and Pettie [SIAM J. Comp. 2020]), no o(log n)-round algorithms are known for the D1LC problem. We give a randomized distributed algorithm for D1LC that is optimal under plausible assumptions about the deterministic complexity of the problem. Using the recent deterministic algorithm of Ghaffari and Kuhn [FOCS2021], our algorithm runs in O(log^3 log n) time, matching the best bound known for (Δ+1)-coloring. In addition, it colors all nodes of degree Ω(log^7 n) in O(log^* n) rounds. A key contribution is a subroutine to generate slack for D1LC. When placed into the framework of Assadi, Chen, and Khanna [SODA2019] and Alon and Assadi [APPROX/RANDOM2020], this almost immediately leads to a palette sparsification theorem for D1LC, generalizing previous results. That gives fast algorithms for D1LC in three different models: an O(1)-round algorithm in the MPC model with Õ(n) memory per machine; a single-pass semi-streaming algorithm in dynamic streams; and an Õ(n√(n))-time algorithm in the standard query model.
READ FULL TEXT