Deterministic Distributed Vertex Coloring: Simpler, Faster, and without Network Decomposition
Mohsen Ghaffari, Fabian Kühn · 2022
We present a simple deterministic distributed algorithm that computes a ($\Delta+1$)-vertex coloring in$O(\text{log}^{2}\Delta. \text{log}\ n)$rounds. The algorithm can be implemented with$O(\text{log}\ n)$-bit messages. The algorithm can also be extended to the more general ($degree+1$)-list coloring problem. Obtaining a polylogarithmic-time deterministic algorithm for ($\Delta +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(\text{log}^{5}n)$-round algorithm for ($\Delta+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 assignments. 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 ($\Delta +1$)-coloring, now reaching the bound of$O(\text{log}^{3}\text{log}\ n)$rounds. As a further application, we provide faster deterministic distributed algorithms for the following vertex coloring variants. In graphs of arboricity$a$, we show that a$(2+\varepsilon)a$-vertex coloring can be computed in$O(\text{log}^{3}a\cdot \text{log} n)$rounds. We also show that for$\Delta\geq 3$, a$\Delta$-coloring of a$\Delta$-colorable graph$G$can be computed in$O(\text{log}^{2}\Delta\cdot \text{log}^{2}n)$rounds.