Communication-Efficient $(1+\epsilon )\Delta$-Edge Coloring and Lovász 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 $\epsilon >0$ and all sufficiently large $\Delta$, we give a public-coin Las Vegas protocol that finds a proper $(1+\epsilon )\Delta$-edge coloring using $O(n{e}^{-\gamma \Delta }+1)$ expected bits and $O\left(\frac{\log n}{\Delta }+1\right)$ expected rounds, where $\gamma >0$ depends only on $\epsilon$. Thus, the expected communication is $o(n)$ when $\Delta =\omega (1)$ and $O(1)$ when $\Delta \ge C_{\epsilon }\log n$, for a sufficiently large constant $C_{\epsilon }$. 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ász 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.