Distributed graph coloring is one of the most extensively studied problems in distributed computing. There is a canonical family of distributed graph coloring algorithms known as the locally-iterative coloring algorithms, first formalized in the seminal work of [Szegedy and Vishwanathan, STOC'93]. In such algorithms, every vertex iteratively updates its own color according to a predetermined function of the current coloring of its local neighborhood. Due to the simplicity and naturalness of its framework, locally-iterative coloring algorithms are of great significance both in theory and practice. In this paper, we give a locally-iterative $(\Delta+1)$-coloring algorithm with $O(\Delta^{3/4}\log\Delta)+\log^*n$ running time. This is the first locally-iterative $(\Delta+1)$-coloring algorithm with sublinear-in-$\Delta$ running time, and answers the main open question raised in a recent breakthrough [Barenboim, Elkin, and Goldberg, JACM'21]. A key component of our algorithm is a locally-iterative procedure that transforms an $O(\Delta^2)$-coloring to a $(\Delta+O(\Delta^{3/4}\log\Delta))$-coloring in $o(\Delta)$ time. Inside this procedure we work on special proper colorings that encode (arb)defective colorings, and reduce the number of used colors quadratically in a locally-iterative fashion. As a main application of our result, we also give a self-stabilizing distributed algorithm for $(\Delta+1)$-coloring with $O(\Delta^{3/4}\log\Delta)+\log^*n$ stabilization time. To the best of our knowledge, this is the first self-stabilizing algorithm for $(\Delta+1)$-coloring with sublinear-in-$\Delta$ stabilization time.
翻译:分布式平面颜色是分布式计算中研究最广泛的问题之一。 本地平面颜色算法在理论和实践上都具有重大意义。 在本文中, 我们给本地平面彩色算法 $( Delta+1) 美元, 首次在[ Szegedy 和 Vishwanathan, STOC' 93] 的开创性工作中正式化。 在这种算法中, 每个顶面都根据当前本地邻居颜色的预设功能, 反复更新自己的颜色 。 由于框架的简单性和自然性, 本地平面彩色算法在理论和实践上都具有重大意义 。 在本地平面彩色算法中, 以本地平面 $- d$- dalta$( Elkin, + Gold_ 4) 内部平面彩色算算法, 以本地平面的 美元- Dal- dal- dal- ta 工作程序, 将我们本地平面平面平面彩色算算法 用于本地平面变色变色算程序。