Distributed Edge Coloring with Small Palettes and a Special Case of the Constructive Lovász Local Lemma

Abstract

We explore the complexity of edge coloring in the LOCAL model in different palette size regimes. 1. Lower Bounds: First, we simplify the 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. Second, we show that a natural approach to computing $(\Delta +1)$-edge colorings (Vizing's theorem) via extending partial colorings by iteratively re-coloring parts of the graph in the worst case requires recoloring subgraphs of diameter $\Omega (\Delta \log n)$. 2. Upper Bounds on General Graphs: 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. Our algorithm employs a permissive version of the constructive Lovasz local lemma as a black box. The runtime of algorithm varies for different choices of $\Delta$ and palette size. For example, our algorithm computes a $(1+\epsilon )\Delta$-edge coloring in $O(\log n)$ time when $\epsilon \ge ({\log }^3\Delta )/\sqrt{\Delta }$, or $O({\log }_{\Delta }n)+(\log \log n{)}^{3+o(1)}$ time when $\epsilon =\Omega (1)$. 3. Upper Bounds on Trees: We show that the $\Omega ({\log }_{\Delta }\log n)$ lower bound can be nearly matched on trees. To establish this result, we develop a new distributed Lovasz local lemma algorithm for tree-structured dependency graphs. Specifically, our $(1+\epsilon )\Delta$-edge coloring algorithm for trees takes $O(\log (1/\epsilon ))\cdot \max \{\frac{\log \log n}{\log \log \log n},{\log }_{\log \Delta }\log n\}$ time when $\epsilon \ge ({\log }^3\Delta )/\sqrt{\Delta }$, or $O\left(\max \{\frac{\log \log n}{\log \log \log n},{\log }_{\Delta }\log n\}\right)$ time when $\epsilon =\Omega (1)$.

References in corpus (1)

• Toward more localized local algorithms: removing assumptions concerning global knowledge

Cited by in corpus (2)

• On the Locality of the Lovász Local Lemma
• Near-Optimal Distributed Ruling Sets for Trees and High-Girth Graphs