Distributed (δ+1)-coloring in linear (in δ) time
Distributed (δ+1)-coloring in linear (in δ) time
复制标题
线性（δ）时间内的分布式（δ+1）着色
DOI：
--
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
Michael Elkin
中科院分区：
文献类型：
--
作者：
Leonid Barenboim;Michael Elkin
分布式（Δ +1）-着色问题是分布式算法中最基本、最有研究价值的问题之一。从86年科尔和维什金的工作开始，有一长串逐渐改进的算法发表。目前最先进的运行时间是O（Δ log Δ + log* n），由于Kuhn和Wattenhofer，PODC'06。Linial（FOCS'87）证明了该问题的下限为1/2 log* n，Szegedy和Vishwanathan（STOC'93）提供了一个启发式论证，表明来自广泛的局部迭代算法家族的算法不太可能实现小于Θ（Δ log Δ）的运行时间。给出了一个运行时间为O（Δ）+ 1/2log * n的确定性（Δ +1）-着色分布式算法.我们还提出了一个运行时间和颜色数之间的折衷，并设计了一个O（Δ · t）-着色算法，其运行时间为O（Δ / t + log* n），对于任意参数t，1 < t ≤ Δ1-ε，对于任意小的常数ε，0 < ε < 1.我们的算法打破了Szegedy和Vishwanathan的启发式障碍，实现了运行时间在最大程度上呈线性Δ。另一方面，Szegedy和Vishwanathan的猜想可能仍然是正确的，因为我们的算法不是来自局部迭代算法家族。在得到这个结果的过程中，我们研究了图着色概念的一个推广，称为亏色。在m-亏p-着色中，顶点被p种颜色着色，使得每个顶点最多有m个邻居具有相同的颜色。我们表明，一个m-亏损p-染色合理小的m和p可以非常有效地计算。我们还发展了一种技术，利用原图G的各种子图的多重亏损染色来计算G的（Δ+1）-染色。我们认为这些技术是独立的利益。
The distributed (Δ + 1)-coloring problem is one of most fundamental and well-studied problems in 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(Δ • t)-coloring algorithm with running time O(Δ / t + log* n), for any parameter t, 1 < t ≤ Δ1-ε, for an arbitrarily small constant ε, 0 < ε < 1. 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 study a generalization of the notion of graph coloring, which is called defective coloring. In an m-defective 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-defective p-coloring with reasonably small m and p can be computed very efficiently. We also develop a technique to employ multiple defective colorings of various subgraphs of the original graph G for computing a (Δ+1)-coloring of G. We believe that these techniques are of independent interest.