The Complexity of Distributed Edge Coloring with Small Palettes

The complexity of distributed edge coloring depends heavily on the palette size as a function of the maximum degree $\Delta$. In this paper we explore the complexity of edge coloring in the LOCAL model in different palette size regimes. 1. We simplify the \emph{round elimination} technique of Brandt et al. and prove that $(2\Delta-2)$-edge coloring requires $\Omega(\log_\Delta \log n)$ time w.h.p. and $\Omega(\log_\Delta n)$ time deterministically, even on trees. The simplified technique is based on two ideas: the notion of an irregular running time and some general observations that transform weak lower bounds into stronger ones. 2. We give a randomized edge coloring algorithm that can use palette sizes as small as $\Delta + \tilde{O}(\sqrt{\Delta})$, which is a natural barrier for randomized approaches. The running time of the algorithm is at most $O(\log\Delta \cdot T_{LLL})$, where $T_{LLL}$ is the complexity of a permissive version of the constructive Lovasz local lemma. 3. We develop a new distributed Lovasz local lemma algorithm for tree-structured dependency graphs, which leads to a $(1+\epsilon)\Delta$-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. 4. A natural approach to computing $(\Delta+1)$-edge colorings (Vizing's theorem) is to extend partial colorings by iteratively re-coloring parts of the graph. We prove that this approach may be viable, but in the worst case requires recoloring subgraphs of diameter $\Omega(\Delta\log n)$. This stands in contrast to distributed algorithms for Brooks' theorem, which exploit the existence of $O(\log_\Delta n)$-length augmenting paths.