Distributed coloring in Õ (√log n) Bit Rounds
Kishore Kothapalli, Christian Scheideler, Melih Onus, Christian Schindelhauer · 2006
We consider the well-known vertex coloring problem: given a graph G, find a coloring of the vertices so that no two neighbors in G have the same color. It is trivial to see that every graph of maximum degree ∆ can be colored with ∆+1 colors, and distributed algorithms that find a (∆+1)coloring in a logarithmic number of communication rounds, with high probability, are known since more than a decade. This is in general the best possible if only a constant number of bits can be sent along every edge in each round. In fact, we show that for the n-node cycle the bit complexity of the coloring problem is Ω(log n). More precisely, if only one bit can be sent along each edge in a round, then every distributed coloring algorithm (i.e., algorithms in which every node has the same initial state and initially only knows its own edges) needs at least Ω(log n) rounds, with high probability, to color the cycle, for any finite number of colors. But what if the edges have orientations, i.e., the endpoints of an edge agree on its orientation (while bits may still flow in both directions)? Does this allow one to provide faster coloring algorithms? Interestingly, for the cycle in which all edges have the same orientation, we show that a simple randomized algorithm can achieve a 3-coloring with only O ( √ log n) rounds of bit transmissions, with high probability (w.h.p.). This re-∗ Supported by NSF grant CCR-0311121. † Partially supported by the DFG-Sonderforschungsbereich 376 and by the EU within 6th Framework Programme under contract 001907 Dynamically