June 8, 2006 - Kishore Kothapalli

Title: Distributed Coloring in Sub-logarithmic Bit Rounds

Abstract:
The talk deals with vertex coloring algorithms: given a graph G, find a coloring of the vertices so that no two neighbors in G have the same color. Distributed algorithms that find a (Delta+1)-coloring in a logarithmic number of communication rounds, with high probability, are known since more than a decade. 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)?

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(sqrt{log n}) rounds of bit transmissions, with high probability (w.h.p.). This result is tight because we also show that the bit complexity of coloring an oriented cycle is Omega(sqrt{log n}), w.h.p., no matter how many colors are allowed. The 3-coloring algorithm can be easily extended to provide a (Delta+1)-coloring for oriented graphs of maximum degree Delta in O(sqrt{log n}) rounds of bit transmissions, w.h.p., if Delta is a constant, and the graph does not contain an oriented cycle of length less than sqrt{log n}. Using more complex algorithms, we show how to obtain an O(Delta)-coloring for arbitrary oriented graphs with maximum degree Delta and with no oriented cycles of length at most sqrt{log n}, using essentially O(log Delta+ sqrt{log n}) rounds of bit transmissions.

Preliminary experimental results also show that the improvement shown analytically translates into practice. This is the first sub-logarithmic bit distributed algorithm for vertex coloring. The results is possible only because we consider oriented edges. Preliminary results reported in this talk appeared as "Distributed Coloring in O(sqrt{log n}) Bit Rounds" in the IEEE International Parallel and Distributed Processing Symposium (IPDPS), 2006.