Diameter-Free Distributed Frequency Control for Graph Coloring in the CONGEST Model

Abstract

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 \ge 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$.

17 pages