A suite of fast randomized distributed algorithms representing varying points on this tradeoff are presented, analyze their properties, and study their time complexity in the sequential, CONGEST and Congested Clique models.
Abstract
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.
The first $poly(\Delta,\log n)-round algorithm for $(\Delta + 1)$-edge coloring in the CONGEST model is presented and the $n$-dependency of its runtime, $\tilde{O}(\log^5 n)$, matches the best published dependency in the LOCAL model.
Sebastian Brandt, Ananth Narayanan, Alexandre Nolin· 0 citations
It is proved that if the number of colors $c$ is not a perfect square, the state-of-the-art defect for distributed $c-colorings by a constant factor in most cases can be improved.
This work generalizes and combines tools from the $(k+2)-coloring to $k$-list-coloring reduction of [Zamir, ICALP 2021] and the hypergraph-containers based approach in [Zamir, STOC 2023] and yields an iterable reduction from $(k+1)$-list-coloring to $k$-list-coloring over fixed palettes.
In this paper, we study proper and complete edge-colorings of Johnson graphs $J(n,2)$, also called $n$-triangular graphs. They are isomorphic both to the 2-token graphs of complete graphs and to the line graphs of complete graphs. A $t$-edge-coloring of a graph $G$ is a function that assigns one color from $\{1,2,\ldots,t\}$ to each edge. Such a coloring is called proper if no two incident edges receive the same color, and complete if every pair of distinct colors appears on a pair of incident edges. The achromatic index, denoted by $\alpha_2(G)$, is the largest integer $t$ for which $G$ admits a proper and complete $t$-edge-coloring. We establish new lower and upper bounds for $\alpha_2(J(n,2))$, provide explicit proper and complete edge-colorings attaining the lower bounds, and determine the exact value of $\alpha_2(J(n,2))$ for several values of $n$.
G. Araujo-Pardo, Cristina Dalf'o, M. Reyes· 0 citations
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$.
This work shows that one can maintain an O(\alpha)-approximate MDS with update time for dynamic graphs whose {\em arboricity} is bounded by $\alpha$ throughout the update sequence, which replaces the dependence on $\Delta$ in prior update bounds with $\alpha$, while also improving the approximation guarantee for bounded-arboricity graphs.