Communication-Efficient $(1+\varepsilon)\Delta$-Edge Coloring and Lov\'asz Local Lemma

Abstract

We study edge coloring in the two-party edge-partition model, where Alice and Bob each know part of the edge set and must jointly produce a proper coloring with little communication. Previous work gave a deterministic $(2\Delta-1)$-edge-coloring protocol using $O(n)$ bits, leaving open whether fewer colors can be obtained efficiently. We simultaneously reduce both the number of colors and the communication. For every fixed $\varepsilon>0$ and all sufficiently large $\Delta$, we give a public-coin Las Vegas protocol that finds a proper $(1+\varepsilon)\Delta$-edge coloring using $O(ne^{-\gamma\Delta} + 1)$ expected bits and $O\left(\frac{\log n}{\Delta}+1\right)$ expected rounds, where $\gamma>0$ depends only on $\varepsilon$. Thus, the expected communication is $o(n)$ when $\Delta=\omega(1)$ and $O(1)$ when $\Delta\ge C_\varepsilon\log n$, for a sufficiently large constant $C_\varepsilon$. Using only private coins adds $O(\log n)$ expected bits. Our key idea is a new randomized coloring procedure that allows Alice and Bob to color their edges using essentially the same color space with only a small amount of coordination, so most of their random choices remain private. To make this procedure succeed, we develop a communication-efficient constructive Lov\'asz local lemma (LLL) for two parties. Our two-party constructive LLL is also of independent interest. We illustrate its broader applicability by applying it to standard LLL formulations of several other classical problems, obtaining communication-efficient two-party protocols.