The Complexity of Distributed Edge Coloring with Small Palettes
Yi‐Jun Chang, Qizheng He, Wenzheng Li, Seth Pettie, Jara Uitto · Society for Industrial and Applied Mathematics eBooks · 2018
The complexity of distributed edge coloring depends heavily on the palette size as a function of the maximum degree Δ. In this paper we explore the complexity of edge coloring in the LOCAL model in different palette size regimes. Our results are as follows. We simplify the round elimination technique of Brandt et al. [9] and prove that (2Δ – 2)-edge coloring requires Ω(logΔ log n) time w.h.p. and Ω(logΔ n) time deterministically, even on trees. The simplified technique is based on two ideas: the notion of an irregular running time (in which network components terminate the algorithm at prescribed, but irregular times) and some general observations that transform weak lower bounds into stronger ones. We give a randomized edge coloring algorithm that can use palette sizes as small as , which is a natural barrier for randomized approaches. The running time of the algorithm is at most O(log Δ · TLLL), where TLLL is the complexity of a permissive version of the constructive Lovász local lemma. We develop a new distributed Lovász local lemma algorithm for tree-structured dependency graphs, which leads to a (1 + ∊)Δ-edge coloring algorithm for trees running in O(log log n) time. This algorithm arises from two new results: a deterministic O(log n)-time LLL algorithm for tree-structured instances, and a randomized O(log log n)-time graph shattering method for breaking the dependency graph into independent O(log n)-size LLL instances. A natural approach to computing (Δ + 1)-edge colorings (Vizing's theorem) is to extend partial colorings by iteratively re-coloring parts of the graph, e.g., via “augmenting paths.” We prove that this approach may be viable, but in the worst case requires recoloring subgraphs of diameter Ω(Δ log n). This stands in contrast to distributed algorithms for Brooks’ theorem [32], which exploit the existence of O(logΔ n)-length augmenting paths.