Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper investigates near-equitable coloring of graphs in distributed networks, focusing on how to achieve color frequencies close to the ideal while minimizing the number of communication rounds. The authors present a suite of fast randomized algorithms that navigate the tradeoff between palette size and frequency accuracy, analyzing their performance across different network models including sequential, CONGEST, and Congested Clique. Key results reveal that these algorithms can efficiently approximate equitable colorings, significantly improving the time complexity over existing methods.
Achieving near-equitable coloring in distributed networks can be done faster than previously thought, with tradeoffs that reveal new insights into communication efficiency.
For an $n$-vertex graph of maximum degree $\Delta$ and diameter $D$, an equitable $(\Delta+1)$-coloring is a vertex coloring where the frequency of each color (namely, the number of vertices it colors) are all equal to $\sigma=n/(\Delta+1)$ (up to rounding). The Hajnal-Szemer\'edi Theorem guarantees the existence of such a coloring for every graph, and an $O(n^2\Delta)$ time sequential algorithm is known for computing such a coloring. Here, we study near-equitable graph coloring in distributed networks. The main question of interest is how close one can remain to the desired palette size of $\Delta+1$ while computing, in few distributed rounds, a coloring whose frequencies are close to $\sigma$. It appears that these two conflicting parameters exhibit a tradeoff, which we attempt to explore. We present a suite of fast randomized distributed algorithms representing varying points on this tradeoff, analyze their properties, and study their time complexity in the sequential, CONGEST and Congested Clique (CC) models.