Deterministic Distributed Vertex Coloring: Simpler, Faster, and without Network Decomposition
share
We present a simple deterministic distributed algorithm that computes a (Δ+1)-vertex coloring in O(log^2 Δ·log n) rounds, in any graph with at most n nodes and maximum degree at most Δ. The algorithm can be implemented with O(log n)-bit messages. It can also be extended to the more general (degree+1)-list coloring problem. Obtaining a polylogarithmic-time deterministic algorithm for (Δ+1)-vertex coloring had remained a central open question in the area of distributed graph algorithms since the 1980s, until a recent network decomposition algorithm of Rozhoň and Ghaffari [STOC '20]. The current state of the art is based on an improved variant of their decomposition, which leads to an O(log^5 n)-round algorithm for (Δ+1)-vertex coloring. Our coloring algorithm is completely different and considerably simpler and faster. It solves the coloring problem in a direct way, without using network decomposition, by gradually rounding a certain fractional color assignment until reaching an integral color assignment. Moreover, via the approach of Chang, Li, and Pettie [STOC '18], this improved deterministic algorithm also leads to an improvement in the complexity of randomized algorithms for (Δ+1)-coloring, now reaching the bound of O(log^3log n) rounds.
READ FULL TEXT