Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper introduces two randomized algorithms for proper graph coloring in the CONGEST model that eliminate the need for diameter-dependent coordination costs. The first algorithm achieves a balance in color frequencies with high probability, using a color palette that scales with the maximum degree and a failure exponent, while the second algorithm provides a frequency cap based on palette slack, ensuring efficient coloring even with fewer colors. Both algorithms operate in logarithmic rounds relative to the network size, significantly improving efficiency in distributed frequency control without diameter constraints.
Achieving proper graph coloring in distributed networks without diameter dependency could revolutionize how we manage color frequencies in large-scale systems.
This paper presents two randomized proper-coloring algorithms that control color frequencies in the synchronous CONGEST model without paying a diameter-dependent coordination cost. Let $\lambda \geq 1$ denote the desired failure exponent. For every fixed $\delta>0$, the first algorithm uses $\chi = \lceil (2+\delta)\Delta \rceil$ colors and, with probability at least $1 - n^{-\lambda}$, outputs a proper coloring that bounds the deviation of every color frequency from $n/\chi$ by $O_\delta(\sqrt{(\lambda+1)(n/\chi)\lg n} + (\lambda+1)\lg n)$. Under an explicit load condition, this additive guarantee yields two-sided relative balance. The second algorithm works with every $\chi>\Delta$ and gives a one-sided frequency cap controlled by the palette slack $\chi - \Delta$. In particular, it uses $\Delta + \lceil (\Delta+1)/\lceil \ln n \rceil \rceil$ colors and caps every used color class by $O((\lambda+1)(\sigma \lg^2 n + \lg n))$, where $\sigma = n/(\Delta+1)$. Both algorithms run in $O((\lambda+1)\lg n)$ rounds, with no dependence on the network diameter; for the first algorithm, the multiplicative constant in the time bound depends on $\delta$.