2020/07/30 by Maus, Yannic, Tonoyan, Tigran · 2 citations
#Data Structures and Algorithms (cs.DS) #Distributed #FOS: Computer and information sciences #Parallel #and Cluster Computing (cs.DC)
paper · doi:10.48550/arxiv.2007.15251
Linial's famous color reduction algorithm reduces a given m-coloring of a graph with maximum degree Δ to a O(Δ2log m)-coloring, in a single round in the LOCAL model. We show a similar result when nodes are restricted to choose their color from a list of allowed colors: given an m-coloring in a directed graph of maximum outdegree β, if every node has a list of size Ω(β2 (log β+loglog m + log log |C|)) from a color space C then they can select a color in two rounds in the LOCAL model. Moreover, the communication of a node essentially consists of sending its list to the neighbors. This is obtained as part of a framework that also contains Linial's color reduction (with an alternative proof) as a special case. Our result also leads to a defective list coloring algorithm. As a corollary, we improve the state-of-the-art truly local (deg+1)-list coloring algorithm from Barenboim et al. [PODC'18] by slightly reducing the runtime to O(√(ΔlogΔ))+log^* n and significantly reducing the message size (from huge to roughly Δ). Our techniques are inspired by the local conflict coloring framework of Fraigniaud et al. [FOCS'16].