* Efficient Randomized Distributed Coloring in CONGEST

Magnús M. Halldórsson $\cdot$<EMAIL_ADDRESS>$\cdot$ Reykjavik University, Iceland

Fabian Kuhn $\cdot$<EMAIL_ADDRESS>$\cdot$ University of Freiburg,
Germany

Yannic Maus $\cdot$<EMAIL_ADDRESS>$\cdot$ Technion, Israel

Tigran Tonoyan $\cdot$<EMAIL_ADDRESS>$\cdot$ Technion, Israel

###### Abstract

Distributed vertex coloring is one of the classic problems and probably also
the most widely studied problems in the area of distributed graph algorithms.
We present a new randomized distributed vertex coloring algorithm for the
standard $\mathsf{CONGEST}$ model, where the network is modeled as an $n$-node
graph $G$, and where the nodes of $G$ operate in synchronous communication
rounds in which they can exchange $O(\log n)$-bit messages over all the edges
of $G$. For graphs with maximum degree $\Delta$, we show that the
$(\Delta+1)$-list coloring problem (and therefore also the standard
$(\Delta+1)$-coloring problem) can be solved in $O(\log^{5}\log n)$ rounds.
Previously such a result was only known for the significantly more powerful
$\mathsf{LOCAL}$ model, where in each round, neighboring nodes can exchange
messages of arbitrary size. The best previous $(\Delta+1)$-coloring algorithm
in the $\mathsf{CONGEST}$ model had a running time of
$O(\log\Delta+\log^{6}\log n)$ rounds. As a function of $n$ alone, the best
previous algorithm therefore had a round complexity of $O(\log n)$, which is a
bound that can also be achieved by a naïve folklore algorithm. For large
maximum degree $\Delta$, our algorithm hence is an exponential improvement
over the previous state of the art.

###### Contents

  1. 1 Introduction
  2. 2 Technical Overview
  3. 3 Top Level Algorithm and Paper Outline
  4. 4 Definitions and Notation
  5. 5 Fast Degree Reduction with RandomColorTrial
  6. 6 Step 1: Initial Slack Generation
  7. 7 Step 2: Coloring Sparse Nodes
  8. 8 Step 3: Coloring Dense Nodes
    1. 8.1 Algorithm Description
    2. 8.2 Degree Reduction for Dense Nodes
    3. 8.3 CONGEST Implementation and Proof of Lemma 8.1
  9. 9 Computation of ACD and Clique Overlay
    1. 9.1 ACD Computation in Congest
    2. 9.2 Clique Overlay for Almost-Cliques
  10. 10 Coloring Small Degree Graphs
  11. A Concentration Bounds

##  1 Introduction

In the distributed vertex coloring problem, we are given an $n$-node network
graph $G=(V,E)$, and the goal is to properly color the nodes of $G$ by a
distributed algorithm: The nodes of $G$ are autonomous agents that interact by
exchanging messages with their neighbors in synchronous communication rounds.
At the end, every node needs to output its color in the computed vertex
coloring. The standard version of the problem asks for a coloring with
$\Delta+1$ colors, where $\Delta$ is the largest degree of $G$, such that the
objective is to match what can be achieved by a simple sequential greedy
algorithm. Distributed coloring has been intensively studied for over 30
years. The problem has been used as a prototypical example to study
distributed symmetry breaking in graphs, and it certainly is at the very core
of the general area of distributed graph algorithms, e.g., [BE13].

#### Distributed Coloring, State of the Art.

The first paper to explicitly study the distributed coloring problem was a
seminal paper by Linial [Lin87], which effectively also started the area of
distributed graph algorithms. Already then, it was known that by using simple
randomized algorithms for the parallel setting [ABI86, Lub86], _with
randomization_ , the distributed $(\Delta+1)$-coloring problem can be solved
in only $O(\log n)$ communication rounds. In fact, even one of the simplest
conceivable randomized distributed coloring algorithms solves the problem in
$O(\log n)$ rounds [Joh99]. The algorithm always maintains a partial proper
coloring and operates in $O(\log n)$ synchronous phases. In each phase, each
uncolored node chooses a uniformly random color among the colors not already
used by some neighbor. A simple analysis shows that each uncolored node can
keep its random color with a constant probability, which leads to the $O(\log
n)$ runtime bound. This most basic random coloring step will also play an
important role in our paper and we will therefore refer to it as
RandomColorTrial in the following.

Classically, distributed coloring was studied in a variant of the message
passing model known as the $\mathsf{LOCAL}$ model, where in each round, nodes
are allowed to exchange messages of arbitrary size. Over the years, the main
challenges have been to understand the deterministic complexity of the
$(\Delta+1)$-coloring problem (e.g., [BE13, BE11, BEK14, Bar16, FHK16, BEG18,
Kuh20]) and to understand to what extent $o(\log n)$-time randomized
distributed coloring algorithms exist. In fact, these two questions are
actually closely related [CKP19]. In a recent breakthrough, Rozhoň and
Ghaffari [RG20] showed that $(\Delta+1)$-coloring (and many other important
problems [GKM17, GHK18]) can deterministically be solved in
$\operatorname{poly\log}(n)$ time. Combined with the astonishing recent
progress on randomized algorithms [BEPS16, EPS15, HSS18, CLP20], this in
particular gives randomized $\operatorname{poly\log\log}(n)$-time algorithms,
with the best complexity known being $O(\log^{5}\log n)$ [GGR21].

With the complexity of distributed coloring in the powerful $\mathsf{LOCAL}$
model being quite well understood, it might now become within reach to also
understand the complexity in the much more realistic $\mathsf{CONGEST}$ model,
where in each round, every node is only allowed to exchange $O(\log n)$ bits
with each of its neighbors. Many early distributed coloring algorithms work
directly in the more restricted $\mathsf{CONGEST}$ model, but the recent
highly efficient randomized algorithms of [EPS15, HSS18, CLP20] unfortunately
make quite heavy use of the power of the $\mathsf{LOCAL}$ model. It seems
unclear whether and to what extent their ideas can be applied in the
$\mathsf{CONGEST}$ model. The best randomized $(\Delta+1)$-coloring algorithm
known in the $\mathsf{CONGEST}$ model has a round complexity of
$O(\log\Delta+\log^{6}\log n)$ [BEPS16, Gha19, GGR21]. Note that as a function
of the number $n$ of nodes alone, this algorithm still has a running time of
$O(\log n)$, which is no faster than the simple 30 years old methods. Given
all the recent progress on distributed coloring, arguably one of the most
important open questions regarding this classic distributed problem is the
following.

Is there a randomized algorithm in the $\mathsf{CONGEST}$ model that solves
the $(\Delta+1)$-vertex coloring problem in time $o(\log n)$ or even in time
$\operatorname{poly\log\log}(n)$?

#### Our Main Contribution.

We answer this question in the affirmative and give a randomized
$(\Delta+1)$-coloring algorithm in the $\mathsf{CONGEST}$ model, which is as
fast as the best known algorithm for the problem in the $\mathsf{LOCAL}$
model. As our main result, we prove the following theorem.

######  Theorem 1.1 (simplified).

There is a randomized distributed algorithm, in the $\mathsf{CONGEST}$ model,
that solves any given instance of the $(\Delta+1)$-list coloring problem in
any $n$-node graph with maximum degree $\Delta$ in $O(\log^{5}\log n)$ rounds,
with high probability.

Note that our algorithm even works for the more general $(\Delta+1)$-list
coloring problem, where every node initially is given an arbitrary list of
$\Delta+1$ colors, and the objective is to find a proper vertex coloring such
that each node is colored with one of the colors from its list.

Our algorithm follows the paradigm of breaking the graph into sparse and dense
parts and processing them separately, which has been the only successful
approach for sublogarithmic complexity in the $\mathsf{LOCAL}$ model [HSS18,
CLP20]. By working in the much more restricted $\mathsf{CONGEST}$ model,
however, we are forced to develop general techniques based on more basic
principles. We show that, under some conditions, the progress guarantee of
RandomColorTrial is exponentially better than suggested by its basic analysis.
Our analysis extends to a general class of random coloring algorithms akin to
RandomColorTrial. For coloring dense parts, however, this has to be combined
with additional techniques to deal with the major challenge of congestion.

In the following, we first give a high level overview over what is known about
randomized coloring algorithms in the $\mathsf{LOCAL}$ model, then briefly
discuss the state of the art in the $\mathsf{CONGEST}$ model. In Section 2, we
overview existing techniques that are relevant to our algorithm, explain in
more detail why it is challenging to use existing ideas in the
$\mathsf{CONGEST}$ model, discuss how we overcome the major challenges, and
summarize the algorithm and the technical ideas of the paper. The core
technical part of the paper starts with and is outlined in Section 3.

#### History of Randomized Coloring in the $\mathsf{LOCAL}$ Model.

The first improvement over the simple $O(\log n)$-time algorithms of [ABI86,
Lub86, Joh99] appeared in [SW10], where the authors show that by trying
several colors in parallel, the $(\Delta+1)$-coloring problem can be solved in
$O(\log\Delta+\sqrt{\log n})$ rounds. A similar result was previously proven
for coloring with $O(\Delta)$ colors in [KSOS06]. Subsequently, the _graph
shattering technique_ , first developed for constructive Lovász Local Lemma
algorithms [Bec91], was introduced by [BEPS16] to the area of distributed
graph algorithms. Since each node is colored with constant probability in each
iteration of RandomColorTrial, $O(\log\Delta)$ iterations suffice to make the
probability of a given node remaining uncolored polynomially small in
$\Delta$. This ensures that afterwards, all remaining connected components of
uncolored nodes are of $\operatorname{poly\log}n$ size, as shown by [BEPS16],
and they are then typically colored by a deterministic algorithm. The
deterministic complexity of coloring $N$-node graphs in the $\mathsf{LOCAL}$
model was at the time $2^{O(\sqrt{\log N})}$ [PS92], but has recently been
improved to $O(\log^{5}N)$ [RG20, GGR21]. As a result, the time complexity of
[BEPS16] improved from $O(\log\Delta)+2^{O(\sqrt{\log\log n})}$ to
$O(\log\Delta+\log^{5}\log n)$. We remark that it was shown in [CKP19] that
for distributed coloring and related problems, the randomized complexity on
graphs of size $n$ is lower bounded by the deterministic complexity on graphs
of size $\sqrt{\log n}$. Hence, in some sense, the graph shattering technique
is necessary.

All further improvements on randomized distributed coloring concentrated on
the “preshattering” part, i.e., on coloring each node with probability
$1-1/\operatorname{poly}(\Delta)$ so that the uncolored nodes form components
of size $\operatorname{poly\log}n$. An important step towards a sublogarithmic
preshattering phase was done by Elkin, Pettie, and Su [EPS15], coloring graphs
satisfying a specific local sparsity property. Following this, Harris,
Schneider, and Su [HSS18] achieved preshattering in time
$O(\sqrt{\log\Delta}+\log\log n)$, resulting in a $(\Delta+1)$-coloring
algorithm with time complexity $O(\sqrt{\log n})$ (in terms of $n$ alone). The
algorithm is based on a decomposition of the graph into locally sparse nodes
to which the algorithm of [EPS15] can be applied and into dense components
that have a constant diameter such that computations within these components
can be carried out in a centralized brute-force manner in the $\mathsf{LOCAL}$
model. Finally, Chang, Li, and Pettie [CLP20] gave a hierarchical version of
the algorithm of [HSS18], bringing the preshattering complexity all the way
down to $O(\log^{*}n)$. This leads to the current best randomized
$(\Delta+1)$-coloring algorithm known with time complexity $O(\log^{5}\log
n)$.

#### State of the Art in the $\mathsf{CONGEST}$ Model.

While the simple RandomColorTrial algorithm and thus the $O(\log\Delta)$
preshattering phase of [BEPS16] clearly also work in the $\mathsf{CONGEST}$
model, the remaining discussed randomized coloring algorithms all use the
additional power of the $\mathsf{LOCAL}$ model to various extents, and if one
aims to achieve similar results for the $\mathsf{CONGEST}$ model, one faces a
number of challenges. The fastest known deterministic algorithm to apply on
$\operatorname{poly\log}(n)$-size components is based on decomposing the graph
into clusters of small diameter (as defined in [AGLP89]), where in the
$\mathsf{LOCAL}$ model, each cluster can be colored in a brute-force way, by
collecting its topology at a single node. Luckily, this issue has already been
solved: The fastest known network decomposition algorithms of [RG20, GGR21]
can directly be applied in the $\mathsf{CONGEST}$ model, and by using
techniques developed in [CHPS17, Gha19, BKM20, HKMN20], one can efficiently
solve the coloring problem in each cluster in the $\mathsf{CONGEST}$ model.
This implies that the $(\Delta+1)$-coloring problem can be solved in
$O(\log\Delta)+\operatorname{poly\log\log}(n)$ rounds. In order to obtain a
sublogarithmic-time $(\Delta+1)$-coloring algorithm in the $\mathsf{CONGEST}$
model, the challenge therefore is to develop an efficient preshattering
algorithm. In Section 2, we discuss how the preshattering techniques used by
[HSS18, CLP20] exploit the power of the $\mathsf{LOCAL}$ model, we describe
the challenges that arise for the $\mathsf{CONGEST}$ model and also how we
tackle those challenges.

##  2 Technical Overview

Although extremely simple, RandomColorTrial lies at the heart of most known
efficient randomized coloring algorithms. Each uncolored node $v$ picks a
uniformly random color $c$ from its current _palette_ – colors from its list
$\Psi(v)$ that are not already used by its neighbors – and then executes
TryColor($v,c$) (Alg. 1). Barenboim, Elkin, Pettie and Su [BEPS16] show that
w.h.p., the _uncolored degree_ (i.e., the degree of the subgraph induced by
uncolored nodes) of every vertex of degree $\Omega(\log n)$ goes down by a
constant factor in each iteration of RandomColorTrial, and within
$O(\log\Delta)$ steps, each node has degree $O(\log n)$.

Algorithm 1 TryColor (vertex $v$, color $c_{v}$)

1: Send $c_{v}$ to $N(v)$, receive the set $T=\\{c_{u}:u\in N(v)\\}$.

2: if $c_{v}\notin T$ then permanently color $v$ with $c_{v}$.

3: Send/receive permanent colors, and remove the received ones from $\Psi(v)$.

Our main technical contribution is a _much faster_ algorithm that partially
colors the input graph so that the uncolored degree reduces to
$\operatorname{poly}\log n$. Once the degree is reduced, one can rely on
efficient $\operatorname{poly}\log\log n$-round algorithms: such algorithms
are well known in the $\mathsf{LOCAL}$ model [BEPS16, RG20, GGR21], and we
discuss their $\mathsf{CONGEST}$ counterparts at the end of this section. Our
degree reduction follows the by-now standard approach of partitioning the
graph into _sparse_ and _dense_ parts to be colored separately, with most of
the action in the dense part. To our knowledge, this approach is the only one
known to have led to sublogarithmic algorithms, even in $\mathsf{LOCAL}$
[HSS18, CLP20]. (It has also been useful in other models of computing, e.g.,
sublinear algorithms and Massively Parallel Computing [PS18, CFG+19, ACK19].)

Algorithms in the $\mathsf{LOCAL}$ model profit from the fact that nodes can
try many colors simultaneously, or can simulate any centralized algorithm in a
small diameter dense part by collecting all the input to one node. These
trivialities in $\mathsf{LOCAL}$ become major challenges in
$\mathsf{CONGEST}$. In the remainder of this section, we describe how we
partition the graph and process sparse and dense parts in $\mathsf{CONGEST}$.

#### Almost-Clique Decompositions.

Inspired by Reed [Ree98], Harris, Schneider, and Su [HSS18] introduced an
important structure, the _almost-clique decomposition_ (ACD). In the variation
we use, it is a partition of $V$ into $V_{sparse},C_{1},C_{2},\ldots,C_{k}$,
where $V_{sparse}$ contains sparse nodes, while each $C_{i}$ is an _almost-
clique_ with the property that each node in $C_{i}$ is adjacent to at least
$(1-\epsilon)\Delta$ other nodes in $C_{i}$, $C_{i}$ contains at most
$(1+\epsilon)\Delta$ nodes, and has diameter at most 2 for a given parameter
$\epsilon<1$. The ACD has been used widely in coloring algorithms in different
models [PS18, CFG+19, ACK19, HKMN20, AA20]. An ACD can be computed in $O(1)$
rounds in the $\mathsf{LOCAL}$ model rather easily, since, roughly speaking,
pairs of nodes can deduce from their common neighborhood size whether they
belong to the same almost-clique or not. Assadi, Chen and Khanna [ACK19] gave
a method that was used in [HKMN20] to compute an ACD in $O(\log n)$ rounds in
$\mathsf{CONGEST}$. Their argument is based on random sampling and requires
$\Omega(\log n)$ time.

We overcome this first obstacle towards a $o(\log n)$ $\mathsf{CONGEST}$
algorithm by showing that such a decomposition can be computed in $O(1)$
rounds via a bootstrapping-style procedure (see Section 9.1). We begin by
sampling a subset $S$ of vertices, where each vertex is independently sampled
w.p. $1/\sqrt{\Delta}$. The idea is to use the whole graph to relay
information between the $S$-nodes, in order to efficiently find out which
pairs of $S$-nodes belong to the same almost-clique (to be constructed). To
this end, each node $v\in V$ chooses a random $S$-neighbor (ID) and broadcasts
it to its neighbors. A key observation is that if two $S$-nodes share many
neighbors, they will likely receive each other’s IDs many times, which allows
them to detect similarity of their neighborhoods. The rest of the nodes join
the structure created by the $S$-nodes to form the partition.

After computing the ACD, our algorithm can then color the sparse nodes in
$V_{sparse}$ and then the dense nodes in $V_{dense}=C_{1}\cup\dots\cup C_{k}$
separately.

#### Coloring Sparse Nodes and Slack Generation.

Schneider and Wattenhofer [SW10] showed that if there are enough colors in the
palettes, the coloring can be extremely quick: e.g.,
$O(\Delta+\log^{1.1}n)$-coloring in $O(\log^{*}\Delta)$ rounds of
$\mathsf{LOCAL}$. In this case, the nodes have plenty of _slack_ : the
difference $S$ between their degree and their palette size is then
$\Omega(\Delta)$. Slack is a property that never decreases (but can increase,
which only makes the problem easier). Suppose we have slack
$S\geq\delta\Delta$, while degrees are clearly bounded by $D\leq\Delta$. After
$O(\log(1/\delta))$ iterations of RandomColorTrial, the nodes have degree at
most $D\leq S/2$. From then on, each node can try $D/(2S)$ random colors in
parallel, which has a failure probability of only $\exp(-D/(2S))$. Thus, the
degrees go down by an _exponential factor_ , $\exp(D/(2S))$, and since the
slack is unchanged, the ratio $D/S$ increases as a tower function, resulting
in $O(\log^{*}\Delta)$ time complexity.

Elkin, Pettie, and Su [EPS15] showed that a single execution of
RandomColorTrial, combined with node sampling, actually generates sufficient
slack in _sparse graphs_. More precisely, if the induced neighborhood graph
$G[N(v)]$ of a node $v$ contains $(1-\tau)\binom{\Delta}{2}$ edges, for some
$\tau=\Omega(\log n/\Delta)$, then after this SlackGeneration step, node $v$
has slack $\Omega(\tau\Delta)$. The reason is that two non-adjacent neighbors
of $v$ have a good chance of being colored with the same color, increasing the
slack: the palette size goes down by only one, while the degree goes down by
two. The coloring of the sparse nodes in [HSS18, CLP20] relies on both
ingredients: First, a single execution of RandomColorTrial produces slack of
$\Omega(\varepsilon^{2}\Delta)$; then the unlimited bandwidth of the
$\mathsf{LOCAL}$ model is used to run a version of the multiple color trials
[SW10, EPS15, CLP20] described above with $\delta=\Theta(\varepsilon^{2})$ in
$O(\log(1/\varepsilon)+\log^{*}\Delta)$ rounds. This works if
$\Delta=\Omega((\log^{2}n)/\varepsilon)$, and otherwise, the graph can be
colored in $O(\log(1/\varepsilon))+\operatorname{poly}\log\log n$ rounds
[BEPS16, GGR21].

The second obstacle is that the multiple trials of [SW10] require large
bandwidth and cannot be performed in $\mathsf{CONGEST}$. We overcome this by
showing that the uncolored degree can be reduced to $O(\log n)$ via
$O(\log\log\Delta)$ iterations of the very simple RandomColorTrial. The
probability of vertex $v$ remaining uncolored after iteration $i$ is about
$d_{i}(v)/|\Psi_{i}(v)|$, where $d_{i}(v)$ is its degree, and $\Psi_{i}(v)$ is
its palette. With a global upper bound $D_{i}$ on $d_{i}(v)$ and a global
lower bound $S$ on the slack as a proxy for palette size, this becomes at most
$D_{i}/S$. In the next iteration $i+1$, $D_{i+1}\leq D_{i}^{2}/S$; hence, the
ratio $D_{i}/S$ satisfies the recurrence $D_{i+1}/S\leq(D_{i}/S)^{2}$. Thus,
the uncolored degree goes down very quickly, and in only $O(\log\log\Delta)$
steps, we are left with a low-degree ($O(\log n)$) graph.

Lemma 5.2 (fast degree reduction, simplified, informal). _Suppose after each
iteration $i$ of a coloring algorithm, every node remains uncolored with
probability at most $D_{i}/S$, even if the random bits of other nodes are
adversarial, for some $D_{i}=\Omega(\log n)$ upper bounding the uncolored
degree in that iteration and $S\geq 2D_{0}$. Then, the series
$\\{\log(S/D_{i}\\}_{i}$ grows geometrically. In particular, after
$O(\log\log\Delta)$ rounds, the uncolored degree becomes $O(\log n)$. _

This powerful observation (in a more general form) will also be crucial for
coloring dense nodes.

#### Coloring Dense Nodes.

Harris, Schneider and Su [HSS18] use the small diameter property of each
almost-clique $C$ to coordinate the coloring choices within $C$. A single
leader node gathers the palettes of all nodes in $C$ and then simulates a
sequential version of RandomColorTrial on a _random ordering_ of $C$ to ensure
that the nodes within $C$ choose different colors. This has the advantage that
only _external neighbors_ of a node $v$, i.e., the neighbors outside of $C$,
conflict with $v$’s choice, reducing the failure probability to
$e(v)/|\Psi(v)|$, where $e(v)$ denotes the _external degree_ of $v$. By the
ACD definition, this external degree is initially at most $\epsilon\Delta$,
while the palette size $|\Psi(v)|$ is $\sim\Delta$, implying a probability to
remain uncolored of $O(\epsilon)$. In order to reduce the uncolored degree,
they repeat these synchronized color trials. Their main effort is to show that
the ratio $E/D$ stays (not much worse than) $\epsilon$ in each repetition,
where $E$ is a global upper bound on external degrees and $D$ lower bounds the
uncolored degree as and thus palette size. Thus, if $\epsilon$ is chosen small
(subconstant), the dense nodes are colored fast, while if $\epsilon$ is large,
the sparse nodes in $V_{sparse}$ are colored fast. The best tradeoff is found
for $\epsilon=\exp(-\Theta(\sqrt{\log\Delta}))$, which yields a time
complexity of $O(\sqrt{\log\Delta})+\operatorname{poly}\log\log n=O(\sqrt{\log
n})$ for coloring sparse and dense nodes.

We use a similar synchronized version of RandomColorTrial as [HSS18] but we
allow the leader to process the nodes in an arbitrary order. The crux of it is
shown as Alg. 2, where $X\subseteq V_{dense}$ is a subset of uncolored dense
nodes that we apply it on (see later), and $X^{C}=X\cap C$ is its share in
each almost-clique. At a high level, our $\mathsf{CONGEST}$ algorithm has a
similar overall structure, with synchronized color selection of nodes within
each almost-clique, while the analysis is quite different.

Algorithm 2 SynchronizedColorTrial ($\mathsf{LOCAL}$ version, informal)

1: Each node $v\in X^{C}$ sends its palette $\Psi(v)$ to its leader $w_{C}$.

2: $w_{C}$ processes the nodes in $X^{C}$ in an _arbitrary order_
$v_{1},v_{2}\dots$, where $v_{j}$ is assigned a candidate color $c_{j}$ chosen
uniformly at random from $\Psi(v)\setminus\\{c_{1},c_{2},\ldots,c_{j-1}\\}$.

3: $w_{C}$ sends each node $v_{j}$ its candidate color $c_{j}$.

4: TryColor($v_{j}$, $c_{j}$), for all $j\geq 1$ in $G[X]$.

One crucial difference of our work from [HSS18] is showing that dense nodes
are colored fast even with _constant_ $\varepsilon$, which effectively
eliminates the need to balance the choice of $\varepsilon$ between sparse and
dense node coloring. Initially, we only care about reducing the external
degree. To this end, we focus on the ratio $e(v)/S_{v}$, where $S_{v}$ is the
slack of node $v$, and we show that it follows the same progression as the
ratio $d_{v}/S_{v}$ did for the sparse nodes. This builds on the following key
structural insight (which only holds for constant $\varepsilon$):

Lemma 6.3. (simplified) _After SlackGeneration, every node $w$ with external
degree $e(w)=\Omega(\log n)$ has slack $\Omega(e(w))$. _

In contrast, [HSS18] does not derive any (initial) slack for dense nodes.

We would now want to apply Lemma 5.2 to shrink the external degrees in
$O(\log\log\Delta)$ iterations of synchronized RandomColorTrial, but we need
to deal first with the heterogeneity in slack and external degrees between
different nodes: although our formal version of Lemma 5.2 is more robust to
heterogeneous slack, it still requires a non-trivial global lower bound on the
slack. One way to achieve this would be to partition $C$ into groups of
roughly equal slack and color those separately. Instead, we put aside a subset
$C^{\prime}\subset C$ of nodes to be colored later, where
$|C^{\prime}|=\Omega(\sqrt{|C|})$.111We use a more subtle partitioning in the
implementation in the $\mathsf{CONGEST}$ model. Each node $v$ in
$R_{0}^{C}=C-C^{\prime}$, the set that we color first, has a lower bound
$|\Psi(v)|\geq|C^{\prime}|$ on palette size throughout the execution of the
algorithm. We can view this as _effective slack_
$ES_{v}=\Omega(\max(e(v),\sqrt{|C|})$. The simplified version of Lemma 5.2
given earlier is extended in the full version to allow for different values
among the nodes. It gives a geometric progression in terms of $\log
ES_{v}/e(v)$, so that after after $O(\log\log\Delta)$ iterations, the external
degree of each node is down to $O(\log n)$, while the effective slack is
$\Omega(\sqrt{|C|})$. After three more rounds, each node remains uncolored
with probability at most $(O(\log n)/\sqrt{|C|})^{3}=O(\log n)/|C|$, resulting
in a low-degree subgraph. We are left with the subgraph $C^{\prime}$, which we
solve recursively, setting aside another subset $C^{\prime\prime}$ with
$|C^{\prime\prime}|=\Omega(|C|^{1/4})$ and coloring
$R_{1}^{C}=C^{\prime}-C^{\prime\prime}$ next. We therefore form _layers_
$R_{1}^{C},R_{2}^{C},\ldots$ that are colored iteratively, which adds another
$\log\log\Delta$ factor to the runtime. As we shall see, these layers have
another advantage that make $\mathsf{CONGEST}$ implementation possible.

We summarize our algorithm for dense nodes in Alg. 3.

Algorithm 3 ColorDenseNodes ($\mathsf{LOCAL}$ version, informal)

1: Partition the uncolored nodes of each almost-clique $C$ into layers
$R^{C}_{0},R^{C}_{1},\ldots,R^{C}_{t}$ (TBD)

2: for $i=0,\dots,t-1$ do

3: for $O(1)$ iterations do RandomColorTrial in $R_{i}$.

4: for $O(\log\log\Delta)$ iterations do SynchronizedColorTrial($R_{i}$).

5: ColorSmallDegreeNodes in $G[V\setminus V_{sparse}]$.

We call RandomColorTrial (in line 3) in order to decrease the external degree
$e(v)$ from $O(S_{v})$ to at most half the slack $S_{v}/2$, as needed to apply
Lemma 5.2.

Even if simplified, there still are several daunting challenges in
implementing our algorithm in $\mathsf{CONGEST}$. In particular, the main
obstacle is the communication requirements for the leader of each almost-
clique to learn the palettes of the nodes, $\Theta(\Delta^{2})$ messages in
$\mathsf{CONGEST}$, of which only $m=O(\Delta)$ can be received per round and
only when sent by $m$ _distinct_ neighbors. Our first step towards overcoming
this obstacle is _sparsifying_ the palette $\Psi(v)$, by transmitting only a
random subset to the leader. This was used earlier in a congested clique
algorithm of Parter and Su [PS18], though on a subgraph that was already
polynomially smaller. The presence of the random put-aside subset
$C^{\prime}=\cup_{i\geq 1}R_{i}^{C}$ of nodes means that it suffices to
transmit only a $O(\log n/|C^{\prime}|)$-fraction of the palette, and yet
SynchronizedColorTrial will have enough randomness in the choice of candidate
colors of nodes in $R_{0}^{C}=C-C^{\prime}$. In general, when coloring layer
$i$, the size of the palette subset to be forwarded is $O(|R_{i}^{C}|)\cdot
O(\log n)/\sum_{j>i}|R_{j}^{C}|=O(\log
n\cdot|R_{i}^{C}|/|R_{i+1}^{C}|)\ll\Delta$, and the total amount of palette
information transmitted to the leader is $O(\log
n\cdot|R_{i}^{C}|^{2}/|R_{i+1}^{C}|)$ colors. We form the layer sizes so that
this is always bounded by $O(\Delta)$.

Note that $O(\Delta)$ colors can be directly sent to the leader only when they
come from $O(\Delta)$ distinct neighbors, which is not the case in our
setting: we need to quickly re-route the messages. This issue is resolved in a
_clique_ by a well known routing strategy of Lenzen [Len13] that allows us to
satisfy arbitrary communication patterns, as long as each node sends/receives
$O(\Delta)$ messages. To make Lenzen’s result usable in an almost-clique $C$,
we compute a _clique overlay_ on $C$, that allows for a simulation of all-to-
all communication, a _congested clique_ , with constant-factor overhead.

Theorem 9.9 (simplified). _There is a $O(\log\log n)$-round $\mathsf{CONGEST}$
algorithm that for any almost-clique $C$, computes a clique overlay, which
simulates all-to-all communication in $C$ with constant-factor runtime
overhead._

Since every almost-clique $C$ has diameter 2, constructing such an overlay
corresponds to finding a relay node $w$ for each non-edge $uv$ in $G[C]$, in a
way that no edge is adjacent to many relays. We reduce this problem to a
coloring problem on a graph with vertices corresponding to non-edges $uv$ in
$G[C]$, and solve it with similar ideas as the coloring of sparse nodes.

Chang, Li, and Pettie [CLP20] build on the argument of [HSS18] and form a
hierarchy of almost clique-decompositions, with epsilons ranging from constant
to $\Delta^{-1/10}$. They divide the nodes into layers, further partition them
into blocks, which are then grouped together into six separate and different
subsets that are tackled with slightly different variations of
SynchronizedColorTrial. In a tour de force, they show how to reduce them in
only a constant number of steps to the setting where their extension of the
multi-trials of [SW10] can take over. The argument is quite delicate, as they
must also ensure along the way that _not too many_ nodes get colored in a
round. While it is not impossible _a priori_ to implement it in
$\mathsf{CONGEST}$, it is likely to be much more difficult than our approach
and not likely to result in a significantly faster method.

The approach of [CLP20] utilizes the unbounded communication bandwidth of the
$\mathsf{LOCAL}$ model in an additional way. The leader gathers also the
topology of the almost-clique, in addition to the palettes of the nodes. We
deal with this by conservatively assuming that $C$ is fully connected when it
comes to candidate color assignment in SynchronizedColorTrial. Namely, we
bound the _anti-degree_ of each node $C$, or its number of _non-neighbors_
within $C$, by the slack of the node, as shown in the full version of Lemma
6.3. The effect of this is roughly equivalent to doubling the external degree,
which does not change the fundamentals.

We believe that our approach yields a simpler and more direct way of obtaining
a $\operatorname{poly}\log\log(n)$-round algorithm for coloring dense nodes,
even in the $\mathsf{LOCAL}$ model.

#### Coloring Small Degree Graphs & Postshattering

After we have reduced the uncolored degree to
$\Delta^{\prime}=\operatorname{poly}\log n$, vertices have already lost colors
from their initial palette, due to colored neighbors; thus, the remaining
problem is a _$(deg+1)$ -list coloring problem_, where the nodes can have
different degrees, and the list of a node of degree $d$ has size at least
$d+1$. Hence, even though our general result (Theorem 1.1) only solves the
$(\Delta+1)$-list coloring problem, it is essential that the following theorem
solves the (possibly harder) $(deg+1)$-list coloring. We use the corresponding
algorithm, called ColorSmallDegreeNodes, to color all remaining vertices in
$O(\log\Delta^{\prime}+\log^{5}\log n)=O(\log^{5}\log n)$ rounds.

Theorem 10.1 (simplified). _$(deg+1)$ -list coloring in a graph with $n$ nodes
and maximum degree $\Delta^{\prime}$ can be solved in
$O(\log\Delta^{\prime}+\log^{5}\log n)$ $\mathsf{CONGEST}$ rounds, w.h.p. _

In the $\mathsf{LOCAL}$ model, an algorithm with the same runtime is known
[BEPS16, RG20, GGR21], and in the $\mathsf{CONGEST}$ model, a
$O(\log\Delta^{\prime}+\log^{6}\log n)$-round algorithm is claimed in [Gha19,
GGR21]. We present a similar (but not identical) algorithm that fixes an error
in the design of a subroutine in [Gha19, GGR21] (see Remark 10.7) and improves
the runtime to match the one in $\mathsf{LOCAL}$.

Our algorithm is obtained by an improved combination of previously known
ideas. It is based on the shattering framework of [BEPS16], which uses
$O(\log\Delta^{\prime})$ iterations of RandomColorTrial to reduce the problem
to coloring connected components of _size_ $N=\operatorname{poly}\log n$, the
_network decomposition_ algorithm from [GGR21], which partitions each such
component into clusters of small _diameter_ ($\operatorname{poly}\log\log n$),
and a $\mathsf{CONGEST}$ algorithm from [Gha19], for list coloring a single
cluster. Interestingly, the latter algorithm is also based on
RandomColorTrial. It simulates $O(\log n)$ independent instances in parallel,
where each instance runs for $O(\log N)$ iterations. One of these instances is
likely to color all vertices of the cluster, and the nodes use the small
diameter to agree on a successful instance.

To simulate many instances in parallel, it is essential that many color trials
can be sent in one $O(\log n)$-bit message. For this, the nodes in a cluster
compute a mapping of the colors in nodes’ palettes to a smaller color space of
size $\operatorname{poly}N$ (cf. [HKMN20]): each color then can be represented
with $O(\log\log n)$ bits, and $O(\log n/\log\log n)$ color trials fit in a
single $\mathsf{CONGEST}$ message.

The bottleneck of our approach is the computation of the network
decomposition, which is also the current bottleneck for faster randomized (and
deterministic) algorithms in the $\mathsf{LOCAL}$ model.

##  3 Top Level Algorithm and Paper Outline

Our main algorithm also serves as an outline of the remainder of the paper.

Algorithm 4 Main Algorithm Outline

1: if $\Delta=O(\log^{4}n)$ then ColorSmallDegreeNodes (Sec. 10) and return

2: ComputeACD Compute an $(\varepsilon,\eta)$-ACD
$V_{sparse},C_{1},\ldots,C_{k}$ of $G$ with $\varepsilon=\frac{1}{3}$,
$\eta=\frac{\varepsilon}{108}$ (Sec. 9)

3: ComputeCliqueOverlay for each $C_{i}$, $1\leq i\leq k$ (Sec. 9.2)

4: Step 1: SlackGeneration (Secs. 5 and 6)

5: Step 2: ColorSparseNodes Color remaining sparse nodes in $G$ (Sec. 7)

6: Step 3: ColorDenseNodes Color remaining dense nodes in $G$ (Sec. 8)

The formal statement of our main result is as follows.

Theorem 1.1. _Let $G$ be the input graph with $n$ vertices and maximum degree
$\Delta$, where each vertex $v$ has a list $\Psi(v)\subseteq[U]$ of
$|\Psi(v)|=\Delta+1$ available colors from a colorspace of size
$U=\operatorname{poly}n$. There is a randomized algorithm that in
$O(\log^{5}\log n)$ rounds in the $\mathsf{CONGEST}$ model, w.h.p.222With high
probability, that is, with probability at least $1-n^{c}$, for any constant
$c\geq 1$. computes a coloring of $G$ such that each vertex $v$ gets a color
from its list $\Psi(v)$._ _The runtime can also be stated as $O(T+\log\log
n+\log^{2}\log\Delta)$, where $T$ is the time needed to $(deg+1)$-list color
an $n$-vertex graph with maximum degree $O(\log^{4}n)$ in a colorspace of size
$\operatorname{poly}n$._

###### Proof sketch.

If $\Delta=O(\log^{4}n)$, then we directly apply algorithm
ColorSmallDegreeNodes from Section 10, to color $G$ in $T$ rounds. Assume that
$\Delta=\omega(\log^{4}n)$. After the ACD computation ($O(1)$ rounds), any
node is either in $V_{sparse}$ or in one of the almost-cliques
$C_{1},\ldots,C_{k}$; thus, any node that is not colored in SlackGeneration
($O(1)$ rounds) gets colored either in ColorSparseNodes ($O(\log\log\Delta+T)$
rounds, cf. Lemma 7.1) or in ColorDenseNodes ($O(\log\log
n+\log^{2}\log\Delta+T)$ rounds, cf. Lemma 8.1), and, all nodes are colored at
the end, w.h.p. The overlay computation takes $O(\log\log n)$ rounds. The
total runtime is dominated by the last step. ∎

##  4 Definitions and Notation

We use $n$ and $\Delta$ to denote the number of nodes and the maximum degree
of the input graph $G$. We let $d_{v}$, $\Psi(v)$, and $N(v)$ (or $N_{H}(v)$,
in a subgraph $H$) denote the degree, palette, and the neighborhood,
respectively, of a node $v$. We often use $s_{v}$ for a lower bound on the
slack (defined below) of node $v$. For simplicity of exposition, we assume in
our analysis that the degree, neighborhood, and palette of a node are always
updated, by removing colored neighbors or colors permanently taken by
neighbors from consideration (which can be done in a single round).

######  Definition 4.1 (similarity, friends, density).

Let $\varepsilon>0$ and $G=(V,E)$ be a graph with maximum degree $\Delta$.
Nodes $u,v\in V$ are _$\varepsilon$ -similar_ if $|N(v)\cap
N(u)|\geq(1-\varepsilon)\Delta$, and are _$\varepsilon$ -friends_, if in
addition $\\{u,v\\}\in E(G)$. Node $u\in V$ is _$\varepsilon$ -dense_ if it
has $(1-\varepsilon)\Delta$ friends.

######  Definition 4.2 (Almost-Clique Decomposition (ACD)).

Let $G=(V,E)$ be a graph and $\varepsilon,\eta\in(0,1)$. A partition
$V=V_{sparse}\cup C_{1}\cup\ldots\cup C_{k}$ of $V$ is an
_$(\varepsilon,\eta)$ -almost-clique decomposition_ for $G$ if:

  1. 1.

$V_{sparse}$ does not contain an $\eta$-dense node ,

  2. 2.

For every $i\in[k]$,
$(1-\varepsilon)\Delta\leq|C_{i}|\leq(1+\varepsilon)\Delta$ ,

  3. 3.

For every $i\in[k]$ and $v\in C_{i}$, $|N(v)\cap
C_{i}|\geq(1-\varepsilon)\Delta$ .

We refer to $C_{i}$ as _$\varepsilon$ -almost-cliques_, omitting $\varepsilon$
when clear from the context. For a node in an almost clique $C_{i}$, the
_antidegree_ – the number of non-neighbors in $C_{i}$ – and _external degree_
– the number of neighbors in other almost cliques $C_{j}$, $j\neq i$ – are key
parameters that we will use.

######  Definition 4.3.

The _external degree_ $e(v)$ of a node $v\in C_{i}$ is
$e(v)=|N(v)\cap\cup_{j\neq i}C_{j}|$. The _antidegree_ $a(v)$ of a node $v\in
C_{i}$ is $a(v)=|C_{i}\setminus N(v)|$.

Lemma 4.5 states useful properties of almost-cliques that easily follow from
the ACD definition. In Section 9, we show how to compute ACD, for some
constants $\varepsilon,\eta$, in $O(1)$ rounds.

######  Observation 4.4.

Let $a,b,c\in(0,1)$. Let $A,B,C$ be three sets. If $|A\cap C|\geq(1-a)\Delta$,
$|B\cap C|\geq(1-b)\Delta$, and $|C|\leq(1+c)\Delta$, then $|A\cap B\cap
C|\geq(1-a-b-c)\Delta$.

######  Lemma 4.5 (ACD properties).

Let $C\in\\{C_{1},\dots,C_{k}\\}$ and $u,v\in C$. It holds that: (i) $u$ and
$v$ are $3\varepsilon$-similar, (ii) $C$ has diameter 1 or 2, (iii) $u$ is
$3\varepsilon$-dense, (iv) $e(u)\leq\varepsilon\Delta$, and (v) for every
$w\in C^{\prime}\neq C$, $|N(u)\cap N(w)|\leq 2\varepsilon\Delta$.

###### Proof.

By the definition of ACD, $|N(u)\cap C|,|N(v)\cap
C|\geq(1-\varepsilon)\Delta$, and $|C|\leq(1+\varepsilon)\Delta$; hence, by
Obs. 4.4, $|N(u)\cap N(v)\cap C|\geq(1-3\varepsilon)\Delta$. This implies (i)
and (ii) (since $u$ and $v$ have a common neighbor in $C$). (iii) follows from
(i) and the bound $|N(u)\cap C|\geq(1-\varepsilon)\Delta$. (iv) follows from
Def. 4.2, 3, using $d_{v}\leq\Delta$. For (v), consider $u\in C$ and $w\in
C^{\prime}$. We have $|N(u)\cap C|,|N(w)\cap
C^{\prime}|\geq(1-\varepsilon)\Delta$, and since $C\cap C^{\prime}=\emptyset$,
it follows that $|N(u)\cap N(w)|<2\varepsilon\Delta$. ∎

######  Definition 4.6 (slack).

Let $v$ be a node with a color palette $\Psi(v)$ in a subgraph $H$ of $G$. The
_slack_ of $v$ in $H$ is the difference $|\Psi(v)|-d$, where $d$ is the number
of uncolored neighbors of $v$ in $H$.

##  5 Fast Degree Reduction with RandomColorTrial

This section is devoted to the derivation of the key property of
RandomColorTrial that our algorithms rely on – fast degree reduction. Recall
that in RandomColorTrial, every node $v$ picks a color $c_{v}\in\Psi(v)$
independently, uniformly at random, and calls TryColor($v$, $c_{v}$) (Alg. 1).
We use $N(v)$ to denote the set of uncolored neighbors of node $v$ in $G$.

We begin by observing that, generally, the algorithm provides a constant
coloring rate, that is, in a large enough subset, a constant fraction of nodes
are colored after a single application.

######  Lemma 5.1.

Let $S$ be a subset of at least $c\log n$ nodes, each node $v\in S$ having
palette of size $|\Psi(v)|\geq c\log n$, for a large enough constant $c>0$.
After a single application of RandomColorTrial, at least $|S|/9$ nodes in $S$
are colored, w.h.p.

###### Proof.

It is shown in [BEPS16, Lemma 5.4] that under the conditions of our lemma, if
$|N(v)|\geq(c/2)\log n$ holds for all nodes in $S$, then at least $|S|/16$
nodes in $S$ are colored in RandomColorTrial, w.p.
$1-n^{-c/1024}-n^{-c/32+1}$. To prove our lemma, we partition $S$ into two
subsets $S_{1}$ and $S_{2}=S\setminus S^{\prime}$, where $S_{1}=\\{v\in
S:|N(v)|\geq|\Psi(v)|\\}$. Let $S^{\prime}$ be the larger of the two; note
that $|S^{\prime}|\geq(c/2)\log n$. If $S^{\prime}=S_{1}$, then by the
reasoning above, for a large enough $c$, it holds w.h.p. that
$|S^{\prime}|/16\geq|S|/32$ nodes in $S$ are colored. Otherwise,
$|\Psi(v)|\geq 2|N(v)|$ holds, for every node $v\in S^{\prime}$. It is easy to
see that in this case, every node in $S$ is successfully colored w.p. at least
1/2, even under an adversarial assignment of colors to its neighbors; hence
Chernoff bound (6) implies that w.p. $1-n^{-c/16}$, at least
$|S^{\prime}|/4=|S|/8$ nodes in $S^{\prime}$ are colored. This completes the
proof. ∎

Next, we show that if nodes have large enough slack, then RandomColorTrial
reduces the degrees of nodes very rapidly. We state the following lemma in a
general form, as it is also used in Section 8 for a more involved color trial
process.

######  Lemma 5.2 (fast degree reduction).

Let $H$ be a subgraph of $G$. For a vertex $v\in H$, let $d_{v}$ be its degree
and $s_{v}\geq 2d_{v}$ be a parameter such that $s_{v}\geq c\log n$, for a
large enough constant $c>0$. Assume the nodes in $H$ execute a randomized
coloring algorithm where in every round $i$, each uncolored node picks a color
different from its neighbors’ choices and makes it its permanent color w.p. at
least $1-|N_{i}(v)|/s_{v}$, irrespective of the color choices of other nodes,
where $N_{i}(v)$ is the set of uncolored neighbors of $v$ in $H$ at the
beginning of round $i$. After $O(\log\log s^{*})$ iterations, every node $v$
in $H$ has at most $O((s_{v}/s^{*})\log n)$ uncolored neighbors in $H$, where
$s^{*}=\min_{w}s_{w}$.

###### Proof.

Let $n_{v}^{i}$ be an upper bound (specified below) on the size of $N_{i}(v)$.
Initially, we have $n_{v}^{1}=d_{v}$. As we assumed, node $v$ is colored in
iteration $i$ w.p. at least $1-n_{v}^{i}/s_{v}$, irrespective of the outcome
for other nodes. For each node $u$, let $Z_{u}=1$ if $u$ is not colored in
iteration $i$ and $Z_{u}=0$ otherwise. We have $Pr[Z_{u}=1]\leq
n_{u}^{i}/s_{u}$. Consider a node $v$, and let $Z=\sum_{u\in N_{i}(v)}Z_{u}$.
We have $\mathbb{E}[Z]\leq\sum_{u\in N_{i}(v)}n_{u}^{i}/s_{u}\leq
n_{v}^{i}M_{i},$ where $M_{i}=\max_{u}(n_{u}^{i}/s_{u})$. Since the
probability bound on $Z_{u}$ above holds irrespective of other
$Z_{u^{\prime}}$, we apply Chernoff bound (7) to get

$Pr\left[\sum_{u\in N_{i}(v)}Z_{u}>n_{v}^{i}M_{i}+c^{\prime}\log n\right]\leq
n^{-c^{\prime}/4}\ ,$

for any constant $c^{\prime}>4$. Hence it holds w.h.p. that
$\sum_{N_{i}(v)}Z_{u}\leq n_{v}^{i}M_{i}+c^{\prime}\log n$, and we can set
$n_{v}^{i+1}=n_{v}^{i}M_{i}+c^{\prime}\log n$. Consider a node $w$ with
$n_{w}^{i}/s_{w}\geq M_{i}^{3/2}$. Then we have

$\frac{n_{w}^{i+1}}{s_{w}}=\frac{n_{w}^{i}M_{i}}{s_{w}}+\frac{c^{\prime}\log
n}{s_{w}}\leq M_{i}^{5/3}+\frac{c^{\prime}\log n}{s^{*}}\ .$

The latter implies the recursion $M_{i+1}\leq M_{i}^{3/2}+c^{\prime}\log
n/s^{*}$. Let $i_{0}=O(1)$ be the first index where the recursion holds and
$r=c^{\prime}\log n/s^{*}$. Recall that $M_{i_{0}}\leq 1/4$. Since
$M_{i},r<1$, we have:

$M_{i+1}\leq M_{i}^{3/2}+r\leq M_{i-1}^{(3/2)^{2}}+r^{3/2}+r\leq
M_{i_{0}}^{(3/2)^{i-O(1)}}+\sum_{j=0}^{i}r^{(3/2)^{j}}=M_{i_{0}}^{(3/2)^{i-O(1)}}+\frac{O(\log
n)}{s^{*}}\ .$

Thus, after $i=O(\log\log s^{*})$ iterations we have $M_{i}=\frac{O(\log
n)}{s^{*}}$, i.e., $n_{v}^{i}=\frac{O(s_{v}\log n)}{s^{*}}$, w.h.p. ∎

##  6 Step 1: Initial Slack Generation

Slack generation is based on the following idea. Take a node $v$, and let
$u,w$ be two of its neighbors. Let $u,w$ each choose a random color from its
palette. If either $u$ or $v$ has a palette that significantly differs from
$\Psi(v)$, then it, say $u$, is likely to choose a color not in $\Psi(v)$, and
the slack of $v$ gets increased, if $u$ retains its color. Otherwise, both $u$
and $v$ have many common colors with $v$, and so are likely to both select the
same color, again increasing the slack of $v$, if they retain their colors.
This increase of slack can be attributed to the pair $u,w$. It is possible to
also ensure that nodes are likely to retain the color they pick, by combining
random coloring with node sampling. This leads us to the algorithm called
SlackGeneration, which consists of an execution of RandomColorTrial in a
randomly sampled subgraph $G[S]$. Each node independently joins $S$ w.p.
$p=1/20$.

The following key result, which has appeared in various reincarnations in
[EPS15, HSS18, CLP20, AA20], formalizes the intuition above, showing that
SlackGeneration converts sparsity into slack. We note that none of the known
variants is suitable to our setting: either they are not adapted for list
coloring or the dependence on sparsity is sub-optimal.

The _local sparsity_ $\zeta_{v}$ of a vertex $v$ is defined as
$\zeta_{v}=\frac{1}{\Delta}\left({\Delta\choose 2}-m(N(v))\right)$, where for
a set $X$ of vertices, $m(X)$ denotes the number of edges in the subgraph
$G[X]$. Roughly speaking, $\zeta_{v}$ is proportional to the number of
“missing” edges in the neighborhood of $v$; note that
$0\leq\zeta_{v}<\Delta/2$.

######  Lemma 6.1.

Assume each vertex $v$ has a palette $\Psi(v)$ of size $\Delta+1$. Let $v$ be
a vertex with $\zeta_{v}\geq c\log n$, for a large enough constant $c>0$.
There is a constant $c_{1}>0$ such that after SlackGeneration, $v$ has slack
$Z\geq c_{1}\zeta_{v}$, w.h.p.

###### Proof.

Let $\zeta=\zeta_{v}$. We may assume w.l.o.g. that
$|N(v)|\geq\Delta-\zeta/2\geq 3\Delta/4$, as otherwise $v$ has slack
$\zeta/2$, and we are done. Let $X\subseteq{\binom{N(v)}{2}}$ be the set of
pairs $\\{u,w\\}$ s.t. $\\{u,w\\}$ is not an edge. Under our assumption,
$N(v)$ contains ${\Delta-\zeta/2\choose 2}$ pairs of nodes, of which at most
${\Delta\choose 2}-\zeta\Delta$ are edges, hence
$|X|\geq{\Delta-\zeta/2\choose 2}-{\Delta\choose
2}+\zeta\Delta>\zeta\Delta/2$.

A node $u$ is _activated_ if it is sampled in $S$. Note that every node is
independently activated w.p. $p=1/20$. The rest of the proof is conditioned on
the high probability event that for every node $v$, there are at most
$(4/3)p\Delta=\Delta/15$ nodes activated in $N(v)$ (which easily follows by an
application of Chernoff bound (7)). We use $V(X)=\\{u:\exists w,\\{u,w\\}\in
X\\}$ to denote the vertices that are in at least one pair in $X$. Let
$X_{1}\subseteq X$ be the subset of pairs $\\{u,w\\}$, s.t. at least one
$z\in\\{u,w\\}$ satisfies

$|\Psi(z)\cap\Psi(v)|<(9/10)(\Delta+1)\ ,$ (1)

and let $X_{2}=X\setminus X_{1}$. The case $|X_{1}|\geq|X|/2$ is easier to
handle. Let $V_{1}\subseteq V$ be the set of vertices that are present in a
pair in $X_{1}$ and satisfy (1). Since $|X_{1}|\geq|X|/2\geq\zeta\Delta/4$ and
each $w\in V_{1}$ can give rise to at most $\Delta$ pairs,
$|V_{1}|\geq\zeta/4$. By a Chernoff bound, there is a subset $V^{\prime}_{1}$
of at least $\zeta p/5$ nodes activated in $V_{1}$, w.h.p. (where we use the
assumption that $\zeta/\log n$ is large enough). Let $w\in V^{\prime}_{1}$. As
assumed, $|\Psi(w)\setminus\Psi(v)|>\Delta/10$, and there are at most
$\Delta/15$ activated neighbors of $w$. Thus, $w$ chooses a color
$c\notin\Psi(v)$ and retains it, even when conditioned on arbitrary color
choices of its activated neighbors, w.p. at least $1/10-1/15=1/30$. Thus, we
can apply Chernoff bound (6), to obtain that at least $p\zeta/160$ nodes in
$V_{1}$ choose a color that is not in $\Psi(v)$, w.h.p. (again, we use the
assumption that $\zeta/\log n$ is large enough). This gives the claimed slack
to $v$. Therefore, we continue with the assumption that $|X_{2}|\geq|X|/2$, or
for simplicity, that $X=X_{2}$ and $|X|\geq\zeta\Delta/2$. Thus, for every
pair $\\{u,w\\}\in X$, $|\Psi(w)\cap\Psi(v)|\geq(9/10)\Delta$, and
$|\Psi(u)\cap\Psi(v)|\geq(9/10)\Delta$, and by Obs. 4.4,

$|\Psi(u)\cap\Psi(w)|\geq(4/5)\Delta\ .$ (2)

Let $Z$ be the number of colors in $\Psi(v)$ that are picked by at least one
pair of activated vertices in $X$ and are permanently selected by all these
activated neighbors.

For each pair $\\{u,w\\}\in X$, let $\mathcal{E}_{1}$ be the event that $u$
and $w$ are activated and pick the same color $c$ which is not picked by any
other node in $N(u)\cap N(w)$, and let $\mathcal{E}_{2}$ be the event that the
colors picked by $u$ and $w$ are not picked by any other node in $V(X)$. Let
$Y_{u,w}$ be the binary random variable that is the indicator of the event
$\mathcal{E}_{1}\cap\mathcal{E}_{2}$.

Note that $Z\geq Y=\sum_{\\{u,v\\}\in X}Y_{u,v}$. First, we show that
$Pr[Y_{u,v}=1]=\Omega(1/\Delta)$, which implies that
$\mathbb{E}[Z]\geq\mathbb{E}[Y]=\Omega(|X|/\Delta)=\Omega(\zeta)$.

Note that
$Pr[Y_{u,v}=1]=Pr[\mathcal{E}_{1}\cap\mathcal{E}_{2}]=Pr[\mathcal{E}_{1}]\cdot
Pr[\mathcal{E}_{2}\mid\mathcal{E}_{1}]$. Note that
$Pr[\mathcal{E}_{2}\mid\mathcal{E}_{1}]$ is the probability that no node in
$V(X)\setminus(\\{u,w\\}\cup N(u)\cup N(w))$ picks the color $c$ picked by $u$
and $w$. Since each node independently is activated w.p. $p$, the probability
that a node picks $c$ is $1/(\Delta+1)$, and $|V(X)|\leq\Delta$, we have

$Pr[\mathcal{E}_{2}\mid\mathcal{E}_{1}]\geq(1-p/(\Delta+1))^{\Delta}=\Omega(1)\
.$

Next, consider $Pr[\mathcal{E}_{1}]$. By our assumption above, for every pair
of vertices $u,w$, at most $3p\Delta<\Delta/5$ vertices are activated in
$N(u)\cup N(w)$. By (2), $|\Psi(u)\cap\Psi(w)|\geq(4/5)\Delta$; hence, there
is a set $S_{u,w}$ of at least $(3/5)\Delta$ colors in $\Psi(u)\cap\Psi(w)$
that are not selected by a neighbor in $N(u)\cap N(w)$. Note that
$\mathcal{E}_{1}$ is implied by both $u$ and $w$ being activated and choosing
a color from $S_{u,w}$, hence we have, as claimed,

$Pr[\mathcal{E}_{1}]\geq
p^{2}\cdot\frac{|S_{u,w}|}{|\Psi(u)|}\cdot\frac{1}{|\Psi(w)|}=\Omega(1/\Delta)\
.$

It remains to show that $Z$ is concentrated around its mean. Let $T$ be the
number of colors in $\Psi(v)$ that are picked by at least one pair $(u,w)\in
X$, and $D$ be the number of colors in $\Psi(v)$ that are picked by at least
one pair $(u,w)\in X$ but are not retained by at least one of them. Note that
$Z=T-D$. Moreover, note that both $T$ and $D$ are a function of activation
r.v. and the random color pick of vertices in $V(X)\cup N(V(X))$, and as such
they are (i) $\Theta(1)$-certifiable: for each color picked in $T$, there are
2 nodes in $V(X)$ that “can certify” for it (for $D$, an additional one that
picked the same color), and (ii) $\Theta(1)$-Lipschitz: changing the
color/activation of one vertex can affect $T$ and $D$ by at most 2.

We need to bound $\mathbb{E}[T]$ (which implies the same bound for $D$, as
$D\leq T$). For a given color $c$ and two nodes $u,w\in V(X)$, the probability
that $u$ and $w$ both pick $c$ is at most $1/(\Delta+1)^{2}$. By the union
bound, the probability that $c$ is picked by a pair is at most
$X/(\Delta+1)^{2}$. There are $\Delta+1$ colors in $\Psi(v)$, so the expected
number $T$ of colors that are picked by at least one pair is
$\mathbb{E}[T]\leq X/(\Delta+1)<\zeta$, and since
$\mathbb{E}[Z]=\Omega(\zeta)=\Omega(\mathbb{E}[T])>c_{3}\sqrt{\mathbb{E}[T]}$,
for a large enough constant $c_{3}$, since $\zeta=\Omega(\log n)$. Applying
Lemma A.3, and using these relations, we have

$Pr\left[|T-\mathbb{E}[T]|\geq\mathbb{E}[Z]/10\right]\leq\exp\left(-\Theta(1)\frac{(\mathbb{E}[Z]/10-O(\sqrt{\mathbb{E}[T]}))^{2}}{\mathbb{E}[T]}\right)\leq\exp(-\Omega(\zeta))\
.$

Since $\zeta\geq c_{2}\log n$, for a large enough constant $c_{2}$, we have
that $|T-\mathbb{E}[T]|<\mathbb{E}[Z]/10$, w.h.p. Similarly,
$|D-\mathbb{E}[D]|<\mathbb{E}[Z]/10$, w.h.p. Putting together we see that
w.h.p.,
$Z=T-D\geq\mathbb{E}[T]-\mathbb{E}[D]-\mathbb{E}[Z]/5=(4/5)\cdot\mathbb{E}[Z]=\Omega(\zeta)$.
This completes the proof. ∎

We apply Lemma 6.1 to establish slack for nodes of various densities. Sparse
nodes obtain slack $\Omega(\Delta)$, while more dense nodes have slack
depending on the _external degree_ and _antidegree_. We use a connection of
antidegree and external degree to local sparsity, originally observed in
[HKMN20] for distance-2 coloring.

######  Lemma 6.2.

Let $\eta,\varepsilon\leq 1/3$. For every node $v\in V_{sparse}$,
$\zeta_{v}\geq(\eta^{2}/4)\Delta$. For every node $v\in C=C_{i}$ with
antidegree $a(v)$ and external degree $e(v)$, it holds that
$\zeta_{v}\geq(1-2\varepsilon)a(v)$ and $\zeta_{v}\geq(1-3\varepsilon)e(v)/2$.

###### Proof.

Let $v\in V_{sparse}$. Since $v$ is not $\eta$-dense, there are less than
$(1-\eta)\Delta$ nodes $u\in N(v)$ satisfying $|N(u)\cap
N(v)|\geq(1-\eta)\Delta$. We assume that $d=|N(v)|\geq(1-\eta/5)\Delta$, as
otherwise $\zeta_{v}\geq\eta/10$ follows from the definition of $\zeta_{v}$.
Thus, $v$ has at least $(4\eta/5)\Delta$ neighbors $u$, each having at least
$(4\eta/5)\Delta$ non-neighbors in $N(v)$; therefore
$m(N(v))\leq{\Delta\choose 2}-(8/25)\eta^{2}\Delta^{2}$, and
$\zeta_{v}\geq(8\eta^{2}/25)\Delta\geq(\eta^{2}/4)\Delta$.

Let us consider a node $v\in C=C_{i}$. Each external neighbor $w\in
N(v)\setminus C$ has at most $\varepsilon\Delta$ neighbors in $C$ (by the
definition of ACD). Thus, since $|N(v)\cap C|\geq(1-\varepsilon)\Delta$, $w$
contributes at least $(1-2\varepsilon)\Delta$ non-edges to $G[N(v)]$. In
total, the external neighbors contribute at least $e(v)(1-2\varepsilon)\Delta$
non-edges in $G[N(v)]$, which must be at most $\zeta_{v}\Delta$; hence,
$\zeta_{v}\geq(1-2\varepsilon)e(v)$.

Next, observe that for every node $u\in C\setminus N(v)$, $|N(u)\cap N(v)\cap
C|\geq(1-3\varepsilon)\Delta$, since $|N(u)\cap C|,|N(v)\cap
C|\geq(1-\varepsilon)\Delta$ and $|C|\geq(1+\varepsilon)\Delta$; hence, there
are at least $a(v)\cdot(1-3\varepsilon)\Delta$ edges between $N(v)$ and
$C\setminus N(v)$. On the other hand, by the definition of sparsity, at most
$2\zeta_{v}\Delta$ edges can exit $N(v)$. Thus,
$\zeta_{v}\geq(1-3\varepsilon)a(v)/2$. ∎

The two lemmas above immediately imply the following one.

######  Lemma 6.3.

After SlackGeneration, every node $v\in V_{sparse}$ has slack
$\Omega(\Delta)$, and every node $w\in C_{i}$ with antidegree $a(w)$ and
external degree $e(w)$ such that $a(w)+e(w)\geq c\log n$, for a large enough
constant $c>0$, has slack $\Omega(e(w)+a(w))$, w.h.p.

##  7 Step 2: Coloring Sparse Nodes

We show that given the $(\varepsilon,\eta)$-ACD, the maximum degree of the
graph induced by uncolored nodes in $V_{sparse}$ can be reduced to $O(\log n)$
with $O(\log\log\Delta)$ executions of RandomColorTrial in $G[V_{sparse}]$,
after which we can apply ColorSmallDegreeNodes to finish coloring
$G[V_{sparse}]$. We call this procedure ColorSparseNodes. After slack
generation, each node in $V_{sparse}$ has slack $\Omega(\Delta)$ (see Sec. 6).
Lemma 5.1 shows that in a few iterations, the slack of every node in
$V_{sparse}$ becomes larger than its uncolored degree, after which Lemma 5.2
applies, to show that the degrees of nodes rapidly decrease to $O(\log n)$.

######  Lemma 7.1 (Coloring sparse nodes).

After SlackGeneration, ColorSparseNodes colors all vertices in $V_{sparse}$ in
$O(\log\log\Delta+T)$ rounds, w.h.p., where $T$ is the time needed to
$(deg+1)$-list color an $n$-vertex graph with maximum degree $O(\log^{4}n)$ in
a colorspace of size $\operatorname{poly}(n)$.

###### Proof.

Assume that $\Delta\geq c\log n$, for a large enough constant $c>0$, as
otherwise $G$ can be colored in $T$ rounds, using ColorSmallDegreeNodes. After
slack generation, each node $v\in V_{sparse}$ has slack $s_{v}\geq
s^{*}=c^{\prime}\Delta$, for a constant $c^{\prime}>0$ (Lemma 6.3). Let $w\in
V_{sparse}$ and let $S$ be the set of uncolored neighbors of $w$ in
$G[V_{sparse}]$. Since each node $v\in S$ has a palette of size $|\Psi(v)|\geq
s_{v}\geq cc^{\prime}\log n$, Lemma 5.1 implies that after $O(1)$ rounds,
there are at most $s_{w}/2$ uncolored nodes remaining in $S$, w.h.p. By the
union bound, this holds for all nodes $w\in V_{sparse}$, w.h.p. For the
subsequent rounds, we lower bound the probability for a node $v$ to get
colored, in order to apply Lemma 5.2. In every round $i$, node $v$ picks a
uniformly random color from $\Psi(v)$; hence, conditioned on any colors
selected by its $t_{i}$ participating neighbors, $v$ selects a different color
w.p. at least $(|\Psi(v)|-t_{i})/|\Psi(v)|=1-t_{i}/|\Psi(v)|\geq
1-t_{i}/s_{v}$, using $s_{v}\leq|\Psi(v)|$. Note that the probability bound on
getting colored holds in each iteration as the slack of a node never
decreases; hence, we can indeed apply Lemma 5.2 with parameters
$s_{v}=s^{*}=c^{\prime}\Delta$ (also recall that $s_{v}\geq cc^{\prime}\log
n$). The lemma implies that in $O(\log\log\Delta)$ rounds, the maximum degree
of $G[V_{sparse}]$ reduces to $O(\log n)$, w.h.p. The remaining nodes in
$V_{sparse}$ can be colored in $T$ rounds, using ColorSmallDegreeNodes. ∎

##  8 Step 3: Coloring Dense Nodes

We assume here that the $(\varepsilon,\eta)$-ACD
$V_{sparse},C_{1},\dots,C_{k}$ of $G$, with $\varepsilon=1/3$ and
$\eta=\varepsilon/108$, is given (computed in Alg. 4, line 2), where each
almost-clique $C=C_{i}$ has a designated leader node $w_{C}$ (e.g., the node
with minimum ID), as well as a clique overlay (computed in Alg. 4, line 3). We
further assume that SlackGeneration has been executed (line 4), and Lemma 6.3
applies.

In this section we describe algorithm ColorDenseNodes (Alg. 5) that colors the
vertices in almost-cliques $C_{1},\ldots,C_{k}$. The high level idea is to use
the slack of nodes to reduce the degrees of the subgraph induced by uncolored
dense nodes to $\operatorname{poly}\log(n)$, and then color the remaining
vertices via ColorSmallDegreeNodes (Theorem 10.1). We prove the following
result.

######  Lemma 8.1 (Coloring dense nodes).

After SlackGeneration, ColorDenseNodes colors all vertices in
$C_{1},\dots,C_{k}$ in $O(T+\log\log n+\log^{2}\log\Delta)$ rounds, w.h.p.,
where $T$ is the time needed to $(deg+1)$-list color an $n$-vertex graph with
maximum degree $O(\log^{4}n)$ in a colorspace of size
$\operatorname{poly}(n)$.

We present the algorithm in Sec. 8.1, prove that all dense nodes are colored
in Sec. 8.2, and complete the proof of Lemma 8.1 by proving that the algorithm
can be implemented efficiently in the $\mathsf{CONGEST}$ model in Sec. 8.3.

_We assume_ that $\Delta=\omega(\log^{4}n)$, as otherwise
ColorSmallDegreeNodes gives the lemma.

###  8.1 Algorithm Description

Towards reducing the degrees of nodes, the plan is to first reduce the
external degree of each node to $O(\log n)$, and then reduce the size of each
almost-clique. If there were no edges within the almost-cliques, one could
reduce the external degree of nodes by applying RandomColorTrial
$O(\log\log\Delta)$ times, as we did for coloring sparse nodes (Section 7),
using the fact that each node has slack proportional to its external degree
(by Lemma 6.3). There are two obstacles to this. First, the external degrees
of nodes can be very different, which is problematic when applying the
arguments from Section 5. Second, unfortunately, there are many edges in
almost-cliques.

To overcome the first obstacle, we partition each almost-clique into layers of
carefully chosen sizes and handle them sequentially. This ensures that
although nodes have different external degrees, they have (to some extent)
similar slacks within the subgraph induced by each layer, which is provided by
the uncolored neighbors in subsequent layers that are left to be colored
later.

To overcome the second obstacle, we assign the nodes in each almost-clique
random colors from their palettes _in an arbitrary fixed node order_ ,
ensuring that each node gets a color different from its predecessors (see Alg.
6). A fast implementation of this procedure in the $\mathsf{CONGEST}$ model
poses certain technical challenges. The idea is to collect the palettes of
nodes of an almost-clique into the leader node, which can then choose the
candidate colors and send them back to the nodes. This cannot be done quickly,
even with fast communication via clique overlays. Instead, we show that it
suffices to send a large enough random subset of each palette, and the similar
slack of nodes provided by partitioning also comes in handy here.

After reducing the external degree, a few applications of the color-
assignment-and-trial-in-cliques procedure described above suffices to reduce
the number of neighbors of each node in the given layer to
$\operatorname{poly}\log(n)$. This is achieved due to the internally conflict-
free (for each almost-clique) color assignment of node colors, low external
degree, and large slack.

Algorithm ColorDenseNodes is formally described in Alg. 5. In line 1, we
partition each almost-clique $C=C_{i}$ into $t=O(\log\log\Delta)$ _layers_
$R_{1}^{C},\ldots,R_{t}^{C}$ that are processed iteratively. The partitioning
is done probabilistically, where each vertex independently joins layer
$R_{i}^{C}$ w.p. $p_{i}$. We describe the probability distribution below.
Throughout this section, let $R_{i}=\cup_{j=1}^{k}R_{i}^{C_{j}}$ denote the
set of all vertices of layer $i$. The terms $R_{i},R_{i}^{C}$ will always
denote the corresponding sets of _uncolored_ nodes, that is, nodes that are
permanently colored are automatically removed from these sets.

Algorithm 5 ColorDenseNodes

1: Partition the uncolored nodes of each almost-clique $C$ into layers
$R^{C}_{0},R^{C}_{1},\ldots,R^{C}_{t}$, where each such node joins $R^{C}_{i}$
with probability $p_{i}$, independently of other nodes.

2: for $O(\log\log n)$ iterations do RandomColorTrial in $R_{0}$.

3: ColorSmallDegreeNodes in $G[R_{0}]$.

4: for $i=0,\dots,t-1$ do

5: for $O(1)$ iterations do RandomColorTrial in $R_{i}$.

6: for $O(\log\log\Delta)$ iterations do SynchronizedColorTrial in $R_{i}$.

7: ColorSmallDegreeNodes in $G[V\setminus V_{sparse}]$.

The purpose of RandomColorTrial in line 2, followed by ColorSmallDegreeNodes,
is to reduce the size of $R_{0}^{C}$ by a logarithmic factor (Lemma 8.7),
which is needed for efficient communication using the clique overlay.

When processing each layer, we start with $O(1)$ applications of
RandomColorTrial, with the purpose of increasing the slack by a constant
factor (used in Lemma 8.4). The main action happens in line 6, where
$O(\log\log\Delta)$ applications of SynchronizedColorTrial (described below)
reduce the size of layer $i$, so that each node in $V$ has $O(\log^{2}n)$
neighbors in $R_{i}$. After this we can invoke ColorSmallDegreeNodes to finish
coloring $V\setminus V_{sparse}$. The subgraph induced by the last layer
$R_{t}$ has small degree, so it is handled by ColorSmallDegreeNodes directly.

Alg. 5 is executed on all almost-cliques in parallel (in particular, each
layer is processed in parallel) and all claims (in particular those in Section
8.2) hold for all almost-cliques.

Finally, let us describe the probability distribution for partitioning. Let
$t^{\prime}=\lceil\log_{3/2}\log_{\log n}\sqrt{\Delta}\rceil$, and $t\leq
3\log\log\Delta$, to be specified below. Let $p_{1}=1/\log^{3/2}n$, and, for
$2\leq i\leq t^{\prime}$, let $p_{i}=p_{i-1}^{3/2}$. For $t^{\prime}<i\leq t$,
let $p_{i}=\sqrt{p_{i-1}/\Delta}$, where $t$ is the largest value such that
$p_{t}\geq c\log n/\Delta$, for a sufficiently large constant $c>0$. Finally,
let $p_{0}=1-\sum_{1}^{t}p_{i}$. We let $\Lambda_{i}=\Delta p_{i}$ denote the
(roughly) expected size of $R_{i}^{C}$. The following observation contains all
the properties of the probability distribution that we need.

######  Observation 8.2.

Let $n>16$. For every $c>0$, there is a $c^{\prime}>0$ such that if
$\Delta>c^{\prime}\log^{4}n$, then:

  1. (i)

$t$ is well defined, and $t^{\prime}<t\leq 3\log\log\Delta$,

  2. (ii)

$\Lambda_{0}\geq\Delta/4$,

  3. (iii)

$c\log n\leq\Lambda_{t}\leq c^{2}\log^{2}n$

  1. (iv)

$\Lambda_{i}\geq c\log n$, $0\leq i\leq t$

  2. (v)

$\Lambda_{i}\leq\Lambda_{i+1}^{2}$, $0\leq i<t$, and

  3. (vi)

$\Lambda_{i}\leq\sqrt{\frac{\Delta\Lambda_{i+1}}{\log n}}$, $0<i<t$

###### Proof.

  1. (i)

By the definition of $t^{\prime}$, we have
$p_{t^{\prime}-1}\geq\Delta^{-1/2}$, implying that
$p_{t^{\prime}}\geq\Delta^{-3/4}>c\log n/\Delta$, for $\Delta\geq
c^{4}\log^{4}n$. Thus $t$ is well defined, we have $t>t^{\prime}$ and by $t$’s
definition we have $p_{t}\Delta\geq c\log n$. Also note that
$p_{t^{\prime}}\Delta\leq\sqrt{\Delta}$.

For $t\geq i>t^{\prime}$, we have $p_{t^{\prime}}\Delta\leq\sqrt{\Delta}$,
$p_{i}\Delta=\sqrt{p_{i-1}\Delta}$, and $p_{t}\Delta\geq c\log n$, hence
$t-t^{\prime}\leq\log\log\Delta$. Since $t^{\prime}\leq 2\log\log\Delta$, we
obtain (i).

  2. (ii)

Note that for $1\leq i\leq t^{\prime}$, we have $p_{i}=(\log n)^{-(3/2)^{i}}$,
and since $\log n>4$, it holds that $\sum_{i\leq t^{\prime}}p_{i}<1/4$. For
$i>t^{\prime}$, we have that $p_{i}<1/\sqrt{\Delta}$, and since
$t-t^{\prime}\leq\log\log\Delta$, we have that
$\sum_{i>t^{\prime}}p_{i}<\log\log\Delta/\sqrt{\Delta}\leq 1/2$, if
$\Delta\geq 16$; hence, $p_{0}=1-\sum_{1}^{t}p_{i}\geq 1/4$, and
$\Lambda_{0}\geq\Delta/4$.

  3. (iii)

By the definition of $t$, we have $p_{t}\geq c\log n/\Delta$, and
$\sqrt{p_{t}/\Delta}<c\log n/\Delta$. They imply that $c\log
n\leq\Lambda_{t}<c^{2}\log^{2}n$

  4. (iv)

Follows from the fact that $p_{i}$ is a decreasing sequence, and $p_{t}\geq
c\log n/\Delta$.

  5. (v)

As observed above, $p_{t^{\prime}}\geq\Delta^{-3/4}$. The latter holds for
$i<t^{\prime}$ as well. Then, $p_{i}\geq\Delta^{-3/4}$ implies that
$(p_{i}\Delta)^{4/3}\geq\Delta^{1/3}$ holds for all $0\leq i\leq t^{\prime}$.
Using this in the last inequality, we obtain, for $t^{\prime}>i>0$,

$\Lambda_{i}=p_{i}\Delta=p_{i+1}^{2/3}\Delta=(p_{i+1}\Delta)^{2/3}\cdot\Delta^{1/3}\leq(p_{i+1}\Delta)^{2}=\Lambda_{i+1}^{2}\
.$

For $t>i\geq t^{\prime}$, we have $\Lambda_{i}=\Lambda_{i+1}^{2}$, by the
definition of $p_{i}$. For $i=0$,
$\Lambda_{0}/\Lambda_{1}^{2}=\log^{3}/\Delta<1$.

  6. (vi)

For $0<i<t^{\prime}$, we have

$\Lambda_{i}^{2}=\Delta^{2}p_{i}^{2}=\Delta^{2}p_{i+1}^{4/3}=\Delta\Lambda_{i+1}\cdot
p_{i+1}^{1/3}\leq\Delta\Lambda_{i+1}/\log n,$

since $p_{i+1}=\log^{-(3/2)^{i+1}}n\leq\log^{-3}n$ holds for $i\geq 1$.

For $t>i\geq t^{\prime}$, we have $p_{i}\leq\Delta^{-1/2}$, hence
$\Lambda_{i}\leq\sqrt{\Delta}$. Unrelated, due to
$\Lambda_{i+1}=\sqrt{\Lambda_{i}}$ it suffices to prove
$\Lambda_{i}\leq\sqrt{\Delta/\log n}\cdot\Lambda_{i}^{1/4}$, which reduces to
$\Lambda_{i}\leq(\Delta/\log n)^{2/3}$. The latter holds for
$\Lambda_{i}\leq\sqrt{\Delta}$, since $\Delta>\log^{4}n$. ∎

#### Synchronized Color Trial.

In SynchronizedColorTrial (see Alg. 6), each vertex of $R_{i}^{C}$ is assigned
a random candidate color distinct from those of other nodes in $R_{i}^{C}$,
which it then tries via TryColor. To achieve this, each vertex of $R_{i}^{C}$
selects a random subset $P(v)$ of its palette $\Psi(v)$ and sends $P(v)$ to
the clique leader $w_{C}$, who then locally processes the nodes in $R_{i}^{C}$
in an arbitrary order and assigns each node $v$ a random color from its set
$P(v)$ that is different from the colors assigned to previous nodes. We let
$|P(v)|=\Pi_{i}=c_{P}\max(1,|R_{i}^{C}|/\Lambda_{i+1})\log n$, where $c_{P}>0$
is a large enough constant, specified in Lemma 8.4.

Algorithm 6 SynchronizedColorTrial (executed in $R_{i}^{C}$, for all $C$ in
parallel)

1: Leader $w_{C}$ computes $|R_{i}^{C}|$ and sends it to all nodes in
$R_{i}^{C}$.

2: Each node $v\in R^{C}_{i}$ sends a uniformly random subset
$P(v)\subseteq\Psi(v)$ of size $|P(v)|=\Pi_{i}$ to $w_{C}$.

3: $w_{C}$ processes the nodes in $R_{i}^{C}$ in an arbitrary order
$v_{1},v_{2}\dots$, where $v_{j}$ is assigned a candidate color $c_{j}$ chosen
uniformly at random from $P(v_{j})\setminus\\{c_{1},c_{2},\ldots,c_{j-1}\\}$.

4: $w_{C}$ sends each node $v_{j}$ its candidate color $c_{j}$.

5: TryColor($v_{j}$, $c_{j}$) in $G[R_{i}]$, for all $j\geq 1$.

We show in Section 8.3 that one iteration of SynchronizedColorTrial can be
implemented in the $\mathsf{CONGEST}$ model in $O(1)$ rounds, using the
_clique overlay_ computed in step 3 of Alg. 4. Note that this is nearly
trivial to do in the $\mathsf{LOCAL}$ model, as any node in $R_{i}^{C}$ is
within distance $2$ from the clique leader $w_{C}$. Further, each node can
send its whole palette $\Psi(v)$ to the leader, which simplifies the analysis.

###  8.2 Degree Reduction for Dense Nodes

We now prove that $O(\log\log\Delta)$ repetitions of SynchronizedColorTrial
(line 6) reduces the external degree of each node in $R_{i}$, and 2 more
iterations reduce the number of neighbors of each node $u\in V$ in $R_{i}$ to
$O(\log^{2}n)$.

We need the following notation. For $v\in V$, let $r_{i}(v)=N(v)\cap R_{i}$
denote its number of uncolored neighbors in $R_{i}$. For $v\in R_{i}^{C}$, let
$e_{i}(v)$ denote its _external degree_ – its number of uncolored neighbors in
$R_{i}\setminus R_{i}^{C}$ – and $a_{i}(v)$ its _antidegree_ – its number of
non-adjacent nodes in $R_{i}^{C}$. Note that $e_{i}(v),r_{i}(v)$ and
$a_{i}(v)$ may change during the execution of the algorithm, but only
downwards.

We begin by bounding the size of $R^{C}_{i}$, as well as various degrees of
nodes, restricted to $R_{i}^{C}$, immediately after the partitioning.

######  Lemma 8.3.

Let $C$ be an almost-clique, and $0\leq i\leq t$. After line 1 of Alg. 5, it
holds w.h.p. that: (i) $|R_{i}^{C}|=\Theta(\Lambda_{i})$, (ii)
$r_{i}(u)=O(\Lambda_{i})$, for $u\in V$, (iii) $|N(v)\cap
R_{i}^{C}|=\Theta(\Lambda_{i})$ and $e_{i}(v)=O(\Lambda_{i})$, for $v\in C$.

###### Proof.

Initially, $|C|=(1\pm\varepsilon)\Delta$, and each node $v\in C$ has at least
$(1-\varepsilon)\Delta$ neighbors in $C$. Before partitioning, a node in $C$
can only be colored in SlackGeneration, where it participates with probability
$p=\frac{1}{20}$. Thus, every node $v\in C$ joins $R^{C}_{i}$ w.p.
$p^{\prime}_{i}\geq\frac{19p_{i}}{20}$, and similarly, every node $v\in
V\setminus V_{sparse}$ joins $R_{i}$ independently w.p. $p^{\prime}_{i}$. The
expected size of $R_{i}^{C}$, as well as the expected number of neighbors of a
vertex $v\in C$ in $R^{C}_{i}$ is $\Theta(p_{i}\Delta)=\Theta(\Lambda_{i})$.
Similarly, the expected number of neighbors of a node $u\in V$ in $R_{i}$ is
$O(p_{i}\Delta)=O(\Lambda_{i})$. Since $\Lambda_{i}>c\log n$, for a large
enough constant $c$ (Obs. 8.2), all claims follow by using Chernoff bound (6).
(Note that $e_{i}(v)\leq r_{i}(v)$.) ∎

The following lemma highlights how many “free” colors each node in $R_{i}^{C}$
has, both due to its slack, as well as due to the fact that during its
processing, its neighbors in $R_{i+1}^{C}$ stay uncolored.

######  Lemma 8.4 (candidate color assignment).

Let $0\leq i<t$. If $\Pi_{i}=c_{P}\max(1,|R_{i}^{C}|/\Lambda_{i+1})\log n$,
for a large enough constant $c_{P}>0$, then in every iteration of
SynchronizedColorTrial in layer $i$, each node $v\in R_{i}^{C}$ has a palette
of size at least $|R_{i}^{C}|+3e_{i}(v)+\Omega(\Lambda_{i+1})$ and is assigned
a candidate color from $P(v)$, w.h.p., even if conditioned on an arbitrary
color assignment to other nodes in $R_{i}^{C}$.

###### Proof.

Let $v\in C$ be a node. Let $a_{i}(v)=a_{0}$ and $e_{i}(v)=e_{0}$ be the
initial antidegree and external degree of $v$ before slack generation (line 4
in Alg. 4). By Lemma 6.3, after slack generation, $v$ has slack
$c(a_{0}+e_{0})$, for a constant $c>0$, w.h.p. By Lemma 8.3, $v$ also has
$c_{1}\Lambda_{i+1}$ uncolored neighbors in $R_{i+1}^{C}$, for a constant
$c_{1}>0$, w.h.p.; hence, $v$ initially has a palette of size
$|\Psi(v)|\geq|N(v)\cap R_{i}^{C}|+c(a_{0}+e_{0})+c_{1}\Lambda_{i+1}$. If
$a_{0}+e_{0}=\Omega(\log n)$, with a large enough coefficient, then, by Lemma
5.1, after $O(1)$ executions of RandomColorTrial (line 5 in Alg. 5), we have
$a_{i}(v)<ca_{0}$ and $e_{i}(v)<(c/3)e_{0}$, w.h.p., and the palette size in
each subsequent round is

$\displaystyle|\Psi(v)|$ $\displaystyle\geq|N(v)\cap
R_{i}^{C}|+c(a_{0}+e_{0})+c_{1}\Lambda_{i+1}\geq|N(v)\cap
R_{i}^{C}|+a_{i}(v)+3e_{i}(v)+c_{1}\Lambda_{i+1}$
$\displaystyle\geq|R_{i}^{C}|+3e_{i}(v)+c_{1}\Lambda_{i+1}\ .$ (3)

If, on the other hand, $a_{0}+c_{0}=O(\log n)$, then (3) still holds, with a
different constant $c^{\prime}_{1}=c_{1}/4$ in front of $\Lambda_{i+1}$, since
by Obs. 8.2, $\Lambda_{i+1}=\Omega(\log n)$, with a large enough coefficient,
which we can choose so that
$c_{1}\Lambda_{i+1}>4(a_{0}+e_{0})>c_{1}\Lambda_{i+1}/4+3(a_{0}+e_{0})$. Let
$\mathcal{C}$ be the set of colors that the leader assigns to the nodes in
$R_{i}^{C}$ preceding $v$. It follows from (3) that for any set $\mathcal{C}$,
the probability that $P(v)\subseteq\mathcal{C}$ is at most

$\left(\frac{|R_{i}^{C}|}{|R_{i}^{C}|+c_{1}\Lambda_{i+1}}\right)^{|P(v)|}=\left(1-\frac{c_{1}\Lambda_{i+1}}{|R_{i}^{C}|+c_{1}\Lambda_{i+1}}\right)^{|P(v)|}\leq\exp\left(-h\right)\
,$

where $h=c_{1}|P(v)|\Lambda_{i+1}/(c_{1}\Lambda_{i+1}+|R_{i}^{C}|)>c_{3}\log
n$, for a large enough constant $c_{3}>0$, since
$|P(v)|=\Pi_{i}=c_{P}\max(1,|R_{i}^{C}|/\Lambda_{i+1})\log n$, for a large
enough constant $c_{P}>0$. Thus, it holds w.h.p. that the leader assigns $v$ a
color from $P(v)\setminus\mathcal{C}$. ∎

######  Lemma 8.5.

Let $i<t$ and assume $R_{0},\dots,R_{i-1}$ have been colored. After
$O(\log\log\Delta)$ iterations of SynchronizedColorTrial, it holds for every
node $v\in R_{i}^{C}$ that $e_{i}(v)=O(\log n)$, w.h.p.

###### Proof.

The goal is to apply Lemma 5.2 with a suitable subgraph $H$. To obtain $H$
from $G[R_{i}]$ each node $v\in R_{i}^{C}$ removes all but the edges to nodes
in $R_{i}\setminus R_{i}^{C}$. Note that the uncolored degree of a vertex in
$H$ corresponds to its (uncolored) external degree in $G[R_{i}]$. When
restricted to $H$ the algorithm (line 6 in Alg. 5) is still a valid coloring
algorithm, since nodes in $V_{sparse}\cup\cup_{j\neq i}R_{j}$ do not
participate, and pairs of nodes within the same almost-clique $C$ are never
assigned the same color. To apply Lemma 5.2 we need to show that in iteration
$j$ of SynchronizedColorTrial each vertex $v$ gets colored with probability at
least $1-N_{j}(v)/s_{v}$ irrespective of the color choices of other nodes, for
a suitable choice of $s_{v}$, where $N_{j}(v)$ are the uncolored neighbors of
$v$ in iteration $j$ in $H$. We condition the rest of the proof on the high
probability event that every node in $R_{i}$ in every iteration is assigned a
candidate color (due to Lemma 8.4).

Let $v\in R_{i}^{C}$ be a vertex, and consider a fixed iteration of
SynchronizedColorTrial. Let $\mathcal{C}$ be the (random) set of candidate
colors assigned to the nodes of $R_{i}^{C}$ preceding $v$. In the rest of the
paragraph, we condition on an arbitrary outcome of $\mathcal{C}$. By the
assumption above, node $v$ is assigned a candidate color $c_{v}\in
P(v)\setminus\mathcal{C}$. It follows from the randomness of $P(v)$ and the
random choice of the candidate color $c_{v}$, that $c_{v}$ is uniformly
distributed in $\Psi(v)\setminus\mathcal{C}$. Let $\mathcal{C^{\prime}}$ be
the set of colors assigned to the external neighbors of $v$. It follows that
even when conditioned on arbitrary $\mathcal{C^{\prime}}$, $v$ is permanently
colored, i.e., $c_{v}\in\Psi(v)\setminus(\mathcal{C}\cup\mathcal{C^{\prime}})$
holds, w.p. at least $1-|\mathcal{C^{\prime}}|/|\Psi(v)\setminus\mathcal{C}|$.
We know that $|\mathcal{C}|<|R_{i}^{C}|$,
$|\mathcal{C^{\prime}}|\leq|N_{H}(v)|$, and
$|\Psi(v)|\geq|R_{i}^{C}|+3e_{i}(v)+\Omega(\Lambda_{i+1})$ (from Lemma 8.4).
Thus, $v$ gets permanently colored w.p. at least

$1-\frac{|\mathcal{C^{\prime}}|}{|\Psi(v)\setminus\mathcal{C}|}\geq
1-\frac{|N_{j}(v)|}{2e_{i}(v)+\Omega(\Lambda_{i+1})}=1-\frac{|N_{j}(v)|}{s_{v}}\
,$ (4)

irrespective of the candidate color assignments of other nodes in $G$ and
where $s_{v}=2e_{i}(v)+\Omega(\Lambda_{i+1})$.

Since also $d_{v}=|N_{j}(v)|=e_{i}(v)\leq s_{v}/2$ and
$s_{v}=\Omega(\Lambda_{i+1})=\Omega(\log n)$, with a large enough constant
factor (provided by Obs. 8.2), Lemma 5.2 applies with parameters $d_{v}$ and
$s_{v}$. Note that $s_{v}\in O(\Lambda_{i})\cap\Omega(\Lambda_{i+1})$, so
after $O(\log\log\min s_{v})=O(\log\log\Delta)$ iterations, each node in
$R_{i}$ has $e_{i}(v)=O(\max_{u,w\in R_{i}}(s_{u}/s_{w})\cdot\log
n)=O(\Lambda_{i+1}\log n)$, w.h.p.

Now, we bound $e_{i}(v)$ further by applying Lemma 5.2 again with a smaller
upper bound on $\max_{u,w\in R_{i}}(s_{u}/s_{w})$: Let us replace
$s_{v}=\min(s_{v},O(\Lambda_{i+1}\log n))$; note that we still have $s_{v}\geq
2d_{v}=2e_{i}(v)$, as well as $s_{v}=\Omega(\Lambda_{i+1})$, and hence,
$\max_{u,w\in R_{i}}(s_{u}/s_{w})=O(\log n)$. Applying Lemma 5.2 again with
the same reasoning and parameters $d_{v}=e_{i}(v)$ and $s_{v}$, we see that
after $O(\log\log\Delta)$ more iterations, $e_{i}(v)=O(\log^{2}n)$, w.h.p. A
final application of Lemma 5.2 with $d_{v}=e_{i}(v)$ and $s_{v}=O(\log^{2}n)$
implies $e_{i}(v)=O(\log n)$, in $O(\log\log\log n)$ more iterations, w.h.p. ∎

######  Lemma 8.6.

Let $i<t$ and assume $R_{0},\dots,R_{i-1}$ have been colored, and for every
node $v\in R_{i}$, $e_{i}(v)=O(\log n)$. After 2 iterations of
SynchronizedColorTrial, it holds, for every node $u\in V$, that
$r_{i}(u)=O(\log^{2}n)$, w.h.p.

###### Proof.

We condition on the high probability events that for each node $u\in V$,
$r_{i}(u)=O(\Lambda_{i})$ (Lemma 8.3), each $v\in R_{i}^{C}$ has palette size
$|\Psi(v)|\geq|R_{i}^{C}|+3e_{i}(v)+\Omega(\Lambda_{i+1})$ and receives a
candidate color in every iteration (Lemma 8.4). Consider a node $u\in V$ and
an arbitrary iteration of SynchronizedColorTrial. For every neighbor $v\in
N(u)\cap R_{i}$, let $X_{v}$ be a binary random variable that is 1 iff $v$
stays uncolored in the iteration. As it was shown in (4), $Pr[X_{v}=1]\leq
e_{i}(v)/(2e_{i}(v)+\Omega(\Lambda_{i+1}))=O(\log n/\Lambda_{i+1})$, even when
conditioned on an adversarial choice of candidate colors for nodes in
$R_{i}\setminus\\{v\\}$, and hence, when conditioned on arbitrary values of
$X_{u}$, $u\in R_{i}\setminus\\{v\\}$ (since _trying a color_ is
deterministic). Recalling that $r_{i}(u)=O(\Lambda_{i})$, we have
$E\left[\sum_{v\in N(u)\cap R_{i}}X_{v}\right]=\frac{O(\Lambda_{i}\log
n)}{\Lambda_{i+1}}$, and since the latter is $\Omega(\log n)$, an application
of Chernoff bound (7) implies that after the iteration, $r_{i}(u)=|N(u)\cap
R_{i}|=\sum_{v\in N(u)\cap R_{i}}X_{v}=\frac{O(\Lambda_{i}\log
n)}{\Lambda_{i+1}}$, w.h.p. By the same reasoning ($s_{v}$ does not decrease),
after another iteration, $r_{i}(u)=O(\max(1,\Lambda_{i}\log
n/\Lambda^{2}_{i+1})\log n)$, w.h.p., which is in $O(\log^{2}n)$, by Obs. 8.2,
(v). ∎

###  8.3 CONGEST Implementation and Proof of Lemma 8.1

All steps in Alg. 5, except for the candidate color assignment, can be
implemented in $\mathsf{CONGEST}$ by design. The computation and distribution
of $|R_{i}^{C}|$ in SynchronizedColorTrial can be done in $O(1)$ rounds using
standard aggregation tools and the fact that $C$ has diameter $2$ (Lemma 4.5).
It remains to show that nodes can indeed send their sets $P(v)$ to their
leader in $O(1)$ $\mathsf{CONGEST}$ rounds, using the clique overlays of
almost-cliques. Recall that colored nodes automatically leave
$R_{i},R_{i}^{C}$, reducing their size.

######  Lemma 8.7.

After line 3 of Alg. 5, $|R_{0}^{C}|<\Delta/\log^{2}n$, w.h.p.

###### Proof.

Initially, $|R_{0}^{C}|=O(\Delta)$. By Lemma 5.1, after each application of
RandomColorTrial in Step 2, the number of nodes in $R_{0}^{C}$ of degree
$\Omega(\log n)$ decreases by a constant factor, w.h.p. Hence, after
$O(\log\log n)$ iterations, it decreases by a factor $O(\log^{2}n)$, w.h.p.
Since we also color (and remove) the small degree vertices in step 3, the size
of $R_{0}^{C}$ shrinks to $\Delta/\log^{2}n$, w.h.p. ∎

######  Lemma 8.8.

W.h.p., in each iteration of SynchronizedColorTrial in $R_{i}^{C}$, $i<t$,
each node succeeds to send a sub-palette $P(v)$ of size $\Pi_{i}$ to leader
$w_{C}$ in $O(1)$ rounds.

###### Proof.

We use the clique overlay of almost-clique $C$, provided by Theorem 9.9,
together with Lenzen’s scheme [Len13]. To this end, we need to ensure that
each node has to send and receive $O(\Delta)$ colors, and that it indeed has
$\Pi_{i}=c_{P}\max(1,|R_{i}^{C}|/\Lambda_{i+1})\log n$ colors in its palette.
The latter follows from Lemma 8.4: each node $v\in R_{i}^{C}$ has palette size
at least
$|R_{i}^{C}|+\Omega(\Lambda_{i+1})=\Omega(\max(1,|R_{i}^{C}|/\Lambda_{i+1})\log
n)$, w.h.p., where the equality holds as long as $\Lambda_{i+1}>c\log n$, for
a large enough constant $c$ (provided by Obs. 8.2).

Consider a fixed iteration of SynchronizedColorTrial. Note that
$\Pi_{i}=O(\Delta)$, since $|R_{i}^{C}|<(1+\varepsilon)\Delta$ and
$\Lambda_{i+1}=\Omega(\log n)$, as observed above; hence, it remains to show
that $w_{C}$ has to receive only $O(\Delta)$ colors. There are $|R_{i}^{C}|$
uncolored nodes in $C$, each sending
$c_{P}\max(1,|R_{i}^{C}|/\Lambda_{i+1})\log n$ colors to $w_{C}$. If
$|R_{i}^{C}|<\Lambda_{i+1}$, then $w_{C}$ has to receive $O(|R_{i}^{C}|\log
n)=O(\Delta)$ colors, since by Lemma 8.7, $|R_{0}^{C}|<\Delta/\log^{2}n$, and
by Lemma 8.3, $|R_{i}^{C}|=O(\Lambda_{i})=O(\Delta/\log n)$, for $i>0$, w.h.p.
Otherwise, $w_{C}$ has to receive $O(|R_{i}^{C}|^{2}\log n/\Lambda_{i+1})$
colors, which again is in $O(\Delta)$: for $i>0$, we have $\Lambda_{i}^{2}\log
n/\Lambda_{i+1}\leq\Delta$, by Obs. 8.2, (vi), while for $i=0$, we have, by
Lemma 8.7, $|R_{0}^{C}|<\Delta/\log^{2}n$, w.h.p., and
$\Lambda_{1}=\Delta/\log^{3/2}n$, so $|R_{0}^{C}|^{2}\log
n/\Lambda_{1}<\Delta$. This completes the proof. ∎

###### Proof of Lemma 8.1.

Lemmas 8.5 and 8.6 imply that w.h.p., after processing layer $i<t$, each node
$u\in V$ has at most $O(\log^{2}n)$ neighbors in $R_{i}$. Similarly, Lemma 8.3
implies that every node $u\in V$ has $O(\Lambda_{t})=O(\log^{2}n)$ neighbors
in $R_{t}$, w.h.p. Altogether, after processing all layers, every node $u\in
V$ has at most $O(t\log^{2}n)=O(\log\log\Delta\cdot\log^{2}n)$ neighbors in
$V\setminus V_{sparse}$; hence, ColorSmallDegreeNodes (line 7) successfully
colors $G[V\setminus V_{sparse}]$, w.h.p.

Partitioning into layers can be done without communication. The preprocessing
in line 2 takes $O(\log\log n)$ rounds, followed by $T$ rounds for
ColorSmallDegreeNodes, which is applied on a graph with $n$ nodes, maximum
degree $\operatorname{poly}\log(n)$ and color space size
$\operatorname{poly}(n)$. We iterate through $O(\log\log\Delta)$ layers, and
each layer makes $O(1)$ iterations of RandomColorTrial (each taking $O(1)$
rounds), followed by $O(\log\log\Delta)$ iterations of SynchronizedColorTrial
(each taking $O(1)$ rounds). Finally, we apply ColorSmallDegreeNodes to a
graph with $n$ nodes, maximum degree $\operatorname{poly}\log(n)$ and color
space size $\operatorname{poly}(n)$. Thus, the runtime is in $O\big{(}\log\log
n+(\log\log\Delta)^{2}+T\big{)}$. ∎

##  9 Computation of ACD and Clique Overlay

###  9.1 ACD Computation in Congest

A distributed algorithm _computes an ACD_ if each $C_{i}$ has a unique AC-ID
that is known to all nodes in $C_{i}$, and each node in $V_{sparse}$ knows it
is in $V_{sparse}$. The goal of the remainder of this section is to prove the
following lemma.

######  Lemma 9.1 (ACD computation).

There is an $O(1)$ round randomized CONGEST algorithm that, given a graph
$G=(V,E)$ with maximum degree $\Delta\geq c\log^{2}n$, for a sufficiently
large constant $c$, computes an $(\varepsilon,\eta)$-ACD with
$\varepsilon=1/3$ and $\eta=\varepsilon/108$, w.h.p.

The algorithm ComputeACD, described in Alg. 7, computes an ACD, using a
bootstrapping-style procedure. We begin by sampling a subset $S$ of vertices,
where each vertex is independently sampled w.p. $1/\sqrt{\Delta}$ (line 1).
The idea is to use the whole graph to relay information between the $S$-nodes,
in order to efficiently find out which pairs of $S$-nodes belong to the same
almost-clique (to be constructed), then let each node $v\in V\setminus S$
decide whether it joins such an $S$-almost-clique $C$, depending on the size
of $N(v)\cap C$. To construct the $S$-almost-cliques, each node $v\in V$
chooses a random $S$-neighbor (ID) and broadcasts it to its neighbors (line
2). A key observation is that if two $S$-nodes are similar, i.e., share many
neighbors, then they will likely receive each other’s IDs many times, which
allows them to detect similarity (with some error), as well as friend edges
(lines 3–4). The $S$-nodes that have detected many friend edges are likely to
be dense, and join a set $S_{dense}$ (line 5). Roughly speaking, the connected
components induced by $S_{dense}$ and detected friend edges form the
$S$-almost-cliques. Each node in $S_{dense}$ selects the minimum ID of an
$S_{dense}$-neighbor and sends it to the other neighbors, thus proposing to
form an almost-clique with that ID (line 6). Each node in $V$ that receives
the same ID from many neighbors also joins the almost-clique with that ID
(line 7). We prove that each connected component $C$ that contains a
sufficiently dense node has the desired properties (w.h.p.):
$|C|\approx\Delta$, and each node $v\in C$ has $\approx\Delta$ neighbors in
$C$. The components not satisfying the required properties are moved into
$V_{sparse}$ (line 8), as they do not contain a dense node (w.h.p.).

Throughout this section we let $\delta=\varepsilon/27<1/80$, and require
$\Delta\geq c\log^{2}n$, for a constant $c>0$, as in Lemma 9.1. Our claims
hold for smaller $\delta$, provided that $\Delta>(c/\delta^{4})\log^{2}n$, for
a large enough constant $c>0$. For any $\gamma\in[0,1]$, we let $F_{\gamma}$
be the set of $\gamma$-friend edges in $G$, and let
$G_{F_{\gamma}}=(V,F_{\gamma})$ be the graph induced by $F_{\gamma}\cup V$.

Algorithm 7 ComputeACD ($\delta\in(0,1/80)$)

1: Sample Each node selects itself into $S$ independently w.p.
$1/\sqrt{\Delta}$ and notifies its neighbors.

2: Gossip Each node $v\in V$ selects uniformly at random one ID of an
$S$-neighbor (if it has any) and forwards it with probability $\min(1,|S\cap
N(v)|/(2\sqrt{\Delta}))$ to each of its $S$-neighbors.

3: Detect similar nodes Each $S$-node $v$ decides it is _approximately
$\delta$-similar_ to node $u$ if $v$ receives the ID of $u$ at least
$(1-2\delta)\sqrt{\Delta}/2$ times.

4: Detect friendship edges The set $F\subseteq E$ consists of the edges
between vertices in $S$ where at least one endpoint identified the other one
as approximately $\delta$-similar.

5: Detect density Each $S$-node with more than $(1-2\delta)\sqrt{\Delta}$
incident $F$-edges joins a set $S_{dense}$.

6: Each node $v\in S_{dense}$ selects the minimum ID of a node $u\in
S_{dense}$ such that $\\{u,v\\}\in F$ and broadcasts it to its neighbors in
$G$.

7: Form cliques Any vertex $v\in V$ (including vertices in $S$) that receives
the same ID at least $(1-11\delta)\sqrt{\Delta}$ times adapts this ID as its
AC-ID, otherwise $v$ joins $V_{sparse}$.

8: Remove bad cliques Use the AC-ID node $w$ of each connected component $C$
as a leader node to ensure: If $|C|<(1-\delta)\Delta$ or there is a node $u\in
C$ with $|N(u)\cap C|<(1-27\delta)\Delta$ then all nodes in $C$ join
$V_{sparse}$.

In the following analysis, we let $H=(S_{dense},F\cap S_{dense}\times
S_{dense})$ denote the subgraph induced by dense nodes ($S_{dense}$) and
friendship edges ($F$). We first show that vertices in $S$ detect friend edges
between them (with some error).

######  Lemma 9.2 ($S$-friend edges are detected).

Let $\delta<1/4$ and $\Delta>(c/\delta^{4})\log^{2}n$, for a large enough
constant $c>0$. W.h.p., (1) any $\delta$-friend edge between vertices in $S$
is contained in $F$, and (2) any edge in $F$ is a $4\delta$-friend edge.

###### Proof.

Let $u,v\in S$, and let $R_{u,v}$ be the set of common neighbors of $u$ and
$v$. The rest of the proof is conditioned on the event that every node in $G$
has at most $(1+\delta)\sqrt{\Delta}$ neighbors in $S$. By Lemma A.2, this
holds w.h.p. (using the bound on $\Delta$). Given this, every node in
$R_{u,v}$ independently sends the ID of $u$ to $v$ w.p. $1/2\sqrt{\Delta}$.
Thus, the expected number of times $v$ receives the ID of $u$ is
$|R_{u,v}|/2\sqrt{\Delta}$.

(1): Assume that $\\{u,v\\}$ is a $\delta$-friend edge. It holds that
$|R_{u,v}|\geq(1-\delta)\Delta$, and hence $v$ receives the ID of $u$ at least
$(1-\delta)\sqrt{\Delta}/2$ times in expectation, and at least
$(1-\delta)^{2}\sqrt{\Delta}/2\geq(1-2\delta)\sqrt{\Delta}/2$ times, w.h.p.,
by a Chernoff bound (6). Claim (1) follows by a union bound over all
$\delta$-dense edges.

(2): Now, assume that $\\{u,v\\}$ is not a $4\delta$-friend edge. Then
$|R_{u,v}|<(1-4\delta)\Delta$, and by a similar application of (7), $v$
receives the ID of $u$ less than
$(1+\delta)|R_{u,v}|/2\sqrt{\Delta}<(1+\delta)(1-4\delta)\sqrt{\Delta}/2\leq(1-2\delta)\sqrt{\Delta}/2$
times, w.h.p. Similarly, $u$ receives the ID of $v$ less than
$(1-2\delta)\sqrt{\Delta}/2$ times, w.h.p. Claim (2) now follows by a union
bound over all edges that are not $4\delta$-dense. ∎

In line 5 of Alg. 7 $S$ nodes use the number of incident friend edges to
detect whether they are dense. The next lemma provides the guarantees of this
step.

######  Lemma 9.3 (Density detection in $S$).

Let $\delta<4$ and $\Delta>(c/\delta^{4})\log^{2}n$, for a large enough
constant $c>0$. W.h.p., (1) if $v\in S$ is $\delta/2$-dense then it is
contained in $S_{dense}$, and (2) if $v\in S$ is not $4\delta$-dense then it
is not contained in $S_{dense}$.

###### Proof.

(1): Let $v$ be a $\delta/2$-dense node and $R_{v}\subseteq N(v)$ be the set
of its $\delta/2$-friends. We know that $|R_{v}|\geq(1-\delta/2)\Delta$. By
Lemma 9.2, all edges $\\{u,v\\}$ with $u\in R_{v}\cap S$ are in $F$, w.h.p. By
Lemma A.2 (using the bound on $\Delta$), $|R_{v}\cap
S|\geq(1-\delta)|R_{v}|/\sqrt{\Delta}\geq(1-\delta)(1-\delta/2)\sqrt{\Delta}\geq(1-2\delta)\sqrt{\Delta}$,
and hence $v$ is in $S_{dense}$, w.h.p. Claim (1) now follows by a union bound
over all $\delta/2$-dense nodes.

(2): Let $v$ be a node that is not $4\delta$-dense. Let $R_{v}\subseteq N(v)$
be the set of $4\delta$-friends of $v$. It holds that
$|R_{v}|<(1-4\delta)\Delta$. By Lemma A.2 (using the bound on $\Delta$),
$|R_{v}\cap S|<(1+\delta)(1-4\delta)\Delta\leq(1-3\delta)\sqrt{\Delta}$,
w.h.p. By Lemma 9.2, for $u\in(N(v)\setminus R_{v})\cap S$ the edge
$\\{u,v\\}$ is not in $F$, w.h.p. Hence, $v$ has at most $|R_{v}\cap
S|<(1-3\delta)\sqrt{\Delta}$ incident edges in $F$, and hence $v$ does not
join $S_{dense}$. Claim (2) now follows by a union bound over all nodes that
are not $4\delta$-dense. ∎

We will use the following observation from [ACK19] in the proof of Lemma 9.5.

######  Observation 9.4 ([ACK19]).

Let $\gamma<1/2$, $v$ be an $\gamma$-dense vertex, and $S_{v}\subseteq N(v)$
be the $(1-\gamma)\Delta$ neighbors of $v$ along $\gamma$-friend edges. Every
vertex in $S_{v}$ is $2\gamma$-dense.

###### Proof.

Let $w,w^{\prime}\in S_{v}$. Since the edges $\\{v,w\\},\\{v,w^{\prime}\\}$
are $\gamma$-friend edges, $|N(w)\cap N(v)|\geq(1-\gamma)\Delta$ and
$|N(w^{\prime})\cap N(v)|\geq(1-\gamma)\Delta$. By Obs. 4.4, $|N(w)\cap
N(w^{\prime})|\geq(1-2\gamma)\Delta$. Similarly, since
$|S_{v}|\geq(1-\gamma)\Delta$ and $|N(w)\cap N(v)|\geq(1-\gamma)\Delta$, we
have $|N(w)\cap S_{v}|\geq(1-2\gamma)\Delta$. Thus, every node in $S_{v}$ has
at least $(1-2\gamma)\Delta$ neighbors in $S_{v}$, all $2\gamma$-similar to
it, i.e., it has at least $(1-2\gamma)\Delta$ of $2\gamma$-friends, as
required. ∎

In the next lemmas we show that the computed components satisfy the properties
of an ACD.

######  Lemma 9.5.

Let $\delta<1/20$ and $\Delta>(c/\delta^{4})\log^{2}n$, for a large enough
constant $c>0$. Let $v$ be a $\delta/4$-dense node in $V$ and $R_{v}$ the set
of its $\delta/4$-friends. All vertices in $R_{v}\cup\\{v\\}$ output the same
AC-ID, w.h.p.

###### Proof.

Fix $v^{\prime}\in R_{v}$ and introduce the following sets:

$\displaystyle R_{v^{\prime}}$ $\displaystyle=R_{v}\cap N(v^{\prime})$
$\displaystyle S_{v,v^{\prime}}$ $\displaystyle=R_{v^{\prime}}\cap S\subseteq
N(v)\cap N(v^{\prime})\cap S$

By Obs. 9.4, all nodes in $R_{v}$ are $\delta/2$-dense and as all nodes in
$S_{v,v^{\prime}}$ are contained in $R_{v}$, Lemma 9.3, (1) implies that
$S_{v,v^{\prime}}\subseteq S_{dense}$. Thus, all nodes in $S_{v,v^{\prime}}$
participate in the ID broadcasting in Step 6. Let $u$ be the node of minimum
ID in $N_{H}(S_{v,v^{\prime}})$, and let $X\subseteq S_{v,v^{\prime}}$ be the
set of nodes that have node $u$ as a neighbor in $H$. By the definition of $u$
(no node in $X$ has a smaller ID neighbor in $H$) all nodes in $X$ forward
$u$’s ID to $v$ and $v^{\prime}$ in Step 6. In the remainder of the proof, we
show that $|X|\geq(1-11\delta)\sqrt{\Delta}$, w.h.p. The claim then follows by
a union bound over all $v^{\prime}$.

Note that $|R_{v}|\geq(1-\delta/4)\Delta$ and $|N(v^{\prime})\cap
N(v)|\geq(1-\delta/4)\Delta$ (since $v,v^{\prime}$ are $\delta/4$-friends),
hence Obs. 4.4 implies that $|R_{v^{\prime}}|\geq(1-\delta/2)\Delta$. Let
$w\in S_{v,v^{\prime}}\subseteq R_{v}$ be a neighbor of $u$ in $H$, i.e.,
$\\{u,w\\}\in F$ ($w$ exists by the definition of $u$). Since $w$ is a
$\delta/4$-friend of $v$, $|N(w)\cap N(v)|\geq(1-\delta/4)\Delta$ holds, and
since $|R_{v^{\prime}}|\geq(1-\delta/2)\Delta$, Obs. 4.4 implies that
$|N(w)\cap R_{v^{\prime}}|\geq(1-\delta)\Delta$.

Therefore, by Lemma A.2 (using the bound on $\Delta$), $|N(w)\cap
S_{v,v^{\prime}}|\geq(1-\delta)^{2}\sqrt{\Delta}\geq(1-2\delta)\sqrt{\Delta}$.
Also by Lemma A.2, $|N(w)\cap S|\leq(1+\delta)\sqrt{\Delta}$. Edge $\\{u,w\\}$
is contained in $F$ (by the definition of $u$ and $w$) and by Lemma 9.2, (2)
it is a a $4\delta$-friend edge, w.h.p. Thus, $|N(w)\cap
N(u)|\geq(1-4\delta)\Delta$. By Lemma A.2, $|N(w)\cap N(u)\cap
S|\geq(1-\delta)(1-4\delta)\sqrt{\Delta}\geq(1-5\delta)\sqrt{\Delta}$.
Applying Obs. 4.4 to sets $C=N(w)\cap S$, $A=N(u)$ and $B=S_{v,v^{\prime}}$,
we see that $|N(w)\cap N(u)\cap
S_{v,v^{\prime}}|\geq(1-8\delta)\sqrt{\Delta}$.

From Lemma A.2, $|N(u)\cap S|\leq(1+\delta)\sqrt{\Delta}$. Let $T$ be the set
of neighbors of $u$ along $F$-edges. Since $u$ is in $S_{dense}$, we have
$|T|\geq(1-2\delta)\sqrt{\Delta}$. Applying Obs. 4.4 with $C=N(u)\cap
S_{v,v^{\prime}}$, $A=T$, and $B=S_{v,v^{\prime}}$, we see that $u$ is
adjacent to at least $(1-11\delta)\sqrt{\Delta}$ nodes in $S_{v,v^{\prime}}$,
along edges belonging to $F$, i.e., $|X|\geq(1-11\delta)\sqrt{\Delta}$. ∎

######  Lemma 9.6.

Let $\delta<1/13$ and $\Delta>(c/\delta^{4})\log^{2}n$, for a large enough
constant $c>0$. Let $C$ be a component with AC-ID $w$, and $v\in C$. W.h.p.,
$|N(v)\cap N(w)|\geq(1-13\delta)\Delta$.

###### Proof.

Let $v$ be a node such that there is a subset $S_{v}\subseteq N(v)\cap
S_{dense}$ of size at least $(1-11\delta)\sqrt{\Delta}$ that broadcast the
same ID $w$ in Step 6. Thus, $w$ and $v$ have $(1-11\delta)\sqrt{\Delta}$
common neighbors in $S$, and hence $|N(v)\cap N(w)|\geq(1-13\delta)\Delta$, as
otherwise by Lemma A.2 (using the bound on $\Delta$), $|N(u)\cap N(w)\cap
S|<(1+\delta)|N(v)\cap N(w)|/\sqrt{\Delta}<(1-11\delta)\sqrt{\Delta}$ (using
$\delta<1/13$), w.h.p. ∎

######  Lemma 9.7 (ACD forming).

Let $\delta<29$ and $\Delta>(c/\delta^{4})\log^{2}n$, for a large enough
constant $c>0$. The following hold w.h.p.:

  1. (1)

every $\delta/4$-dense node in $V$ adapts an AC-ID. For every component $C$
that contains a $\delta/4$-dense node,

  2. (2)

$|C|\geq(1-\delta/4)\Delta$,

  3. (3)

every node $v\in C$ has at least $(1-27\delta)\Delta$ neighbors in $C$,

  4. (4)

$|C|\leq(1+25\delta)\Delta$.

###### Proof.

(1), (2): Immediately follows from Lemma 9.5.

(3): Let $C$ be the component with AC-ID $w$, and $v\in C$ be an arbitrary
node in it. By Lemma 9.6, $|N(v)\cap N(w)|\geq(1-13\delta)\Delta$ holds w.h.p.
Let $u\in C$ be the $\delta/4$-dense node in $C$. We know from Lemma 9.5 that
the set $R_{u}$ of at least $(1-\delta/4)\Delta$ neighbors of $u$ is contained
in $C$. Since $|N(u)\cap N(w)|\geq(1-13\delta)\Delta$ and $|N(v)\cap
N(w)|\geq(1-13\delta)\Delta$, we have $|R_{u}\cap
N(w)|\geq(1-14\delta)\Delta$, and hence $|N(v)\cap N(w)\cap
R_{u}|\geq(1-27\delta)\Delta$. The latter implies the claim since
$R_{u}\subseteq C$.

(4): Following the proof of (3), let $w$ be the AC-ID of a component $C$ whose
size we want to bound. By the definition of the algorithm, every node in $C$
is within distance 2 from $w$. Let $A=N(w)$ and $B=(N(A)\setminus A)\cap C$.
Note that $A\cup B=C$. By Lemma 9.6, for each node $v\in C$, $|N(v)\cap
N(w)|>(1-13\delta)\Delta$, w.h.p. Thus, for each node $u\in A$, $|N(u)\cap
A|\geq(1-13\delta)\Delta$ and hence $|N(u)\cap B|<13\delta\Delta$. On the
other hand, for each node $v\in B$, $|N(v)\cap A|\geq(1-13\delta)\Delta$. The
former implies that the number of edges between $A$ and $B$ is at most
$13\delta|A|$, while the latter implies that it is at least $(1-13\delta)|B|$.
Hence, $|B|<\frac{13\delta}{1-13\delta}|A|<25\delta|A|$ which implies the
claim. ∎

###### Proof of Lemma 9.1.

The output is well-defined: Every node $v$ adopts at most one AC-ID, since by
Lemma A.2, $|N(v)\cap S|\leq(1+\delta)\sqrt{\Delta}$, and
$(1-11\delta)\sqrt{\Delta}>(1+\delta)\sqrt{\Delta}/2$, for $\delta<20$. The
main properties follow immediately from the algorithm definition and Lemma
9.7, recalling that $\delta=\frac{\varepsilon}{27}$.

Steps 1 to 6 clearly take $O(1)$ rounds. Step 7 takes $O(1)$ rounds, since by
the definition of the algorithm, every node in a component with AC-ID $w$ is
within distance 2 from $w$; hence, $w$ can aggregate the size of $C$ and the
degrees of nodes within $C$ in $O(1)$ rounds. ∎

######  Remark 9.8.

The constants in Lemma 4.5 can be improved by deriving the properties claimed
there directly from our algorithm. However, that would make the exposition
more complicated.

###  9.2 Clique Overlay for Almost-Cliques

Consider a $\Delta$-clique $K_{\Delta}$ with a set of _routing requests_ ,
where each node has $O(\Delta)$ messages to send to or receive from other
nodes in $K_{\Delta}$ (a node can have several messages addressed to the same
destination). In his celebrated work, Lenzen [Len13] designed an algorithm
that allows an execution of any given set of routing requests in $O(1)$
$\mathsf{CONGEST}$ rounds. In order to achieve a similar result for almost-
cliques, we simulate a clique over a given almost-clique. Recall that an
almost-clique has diameter 2 (Lemma 4.5). A _clique overlay_ of an almost-
clique $C$ is a collection $O$ of length-2 paths, containing a path between
any pair of non-adjacent nodes in $C$. The _congestion_ of an overlay $O$ is
the maximum, over the edges $e$ of $G$, number of occurrences of $e$ in $C$. A
distributed algorithm computes an overlay $O$ of an almost clique $C$ if for
every non-edge $\\{u,v\\}$ in $C$, nodes $u,v$ know the node $w$ that forwards
messages from $v$ to $u$ and vice versa in $O$.

Given a clique overlay of congestion 2 for an almost clique $C$, we can
combine it with Lenzen’s algorithm to execute in $O(1)$ rounds any given set
of routing requests where each node sends and receives $O(\Delta)$ messages.

We give a randomized algorithm, called ComputeCliqueOverlay, that, for a given
almost clique $C$, computes a clique overlay with congestion 2 in $O(\log\log
n)$ rounds. The main idea is to model the construction of an overlay as a list
coloring problem, where missing edges of $C$ are the vertices of a graph,
while the nodes of $C$ are the colors: a vertex $uv$ picking color $w$ means
$w$ is used in the overlay to forward messages from $u$ to $v$ and back. As we
note below, the runtime can be improved by using slightly more involved
algorithms.

######  Theorem 9.9.

Assume that $\varepsilon\leq 1/15$ and $\varepsilon\Delta>c\log^{2}n$, for a
large enough constant $c>0$. There is a $O(\log\log n)$-round
$\mathsf{CONGEST}$ algorithm that, for any almost-clique $C$ with a leader
node $w_{C}$, computes a clique overlay $O$ of congestion 2.

###### Proof.

We assume the nodes in $C$ know the IDs of all non-neighbors in $C$. This can
be achieved via standard aggregation methods, e.g., by forming a breadth-
first-search tree rooted at the leader $w_{C}$, which aggregates the sizes of
subtrees, and counts and enumerates the nodes from $1$ to $|C|$. As a result,
each node knows its new ID, as well as $|C|$, and in one additional round of
communication, also knows the IDs of its neighbors; hence, it also knows the
IDs of its non-neighbors.

We reduce the construction of a congestion-2 overlay to a coloring problem
with high bandwidth. We form a graph $H$ with a vertex $uv$ for each non-edge
$\\{u,v\\}$ in $G[C]$. Vertices $uv$, $wt$ of $H$ are adjacent if
$\\{u,v\\}\cap\\{w,t\\}\neq\emptyset$. We refer here to vertices of $G$ as
_nodes_ to distinguish from _vertices_ of $H$. The colorspace of our coloring
problem is the set $[|C|]$ of recomputed node IDs in $C$. The initial palette
$\Psi(uv)$ of a vertex $uv$ is the set $N(u)\cap N(v)\cap C$ of common
neighbors of $u$ and $v$ in $C$.

Observe that solving the constructed list coloring instance for $H$ yields a
congestion-2 clique overlay $O$ for $C$. Namely, each non-edge (vertex) $uv$
is assigned a 2-path via some node $w$ (color), and each edge $\\{u,w\\}$ of
$C$ is only used in 2-paths of color $u$ or $w$, and so it appear at most
twice in $O$. Further note that every vertex in $H$ has degree at most
$2\varepsilon\Delta$, while the palette size is at most
$(1-3\varepsilon)\Delta$ (using Obs. 4.4). As a result, assuming that
$\varepsilon\leq 1/15$, each vertex has slack three times larger than its
degree, that is, we have a _sparse node coloring_ instance, with a caveat: the
computation needs to be done in $G[C]$.

We have each vertex $uw$ of $H$ _handled_ by the incident node $u$ with higher
ID. The handler $u$ has an imperfect information about the palette: during the
algorithm, it maintains an _apparent palette_ $\Psi^{\prime}(uv)=\\{w\in
N(u):uw\notin O\\}$, which contains some unusable colors, as $u$ does not know
which of its neighbors $w\in N(u)$ are adjacent to $v$
($\Psi^{\prime}(uv)\setminus\Psi(uv)$ consists of those neighbors that are not
adjacent to $v$). We let the handler nodes simulate RandomColorTrial in $H$,
with the apparent palettes of vertices, but only retain colors that belong to
the original palettes. The execution is done in a sequence of pairs of rounds.
In the first round of each pair, node $u$ picks a uniformly random color
$c_{v}$ from each palette $\Psi^{\prime}(uv)$ for each vertex $uv$ it handles.
If the same color is sampled for two or more vertices $uv,uv^{\prime},\dots$
then they are not colored in this round. For each remaining $uv$, $u$ sends
the ID of $v$ to $c_{v}$ (note that $u$ sends a single message to $c_{v}$). In
the second round of the pair, consider a node $w$ that receives node IDs
$v_{1},v_{2},\dots,v_{t}$ from neighbors $u_{1},u_{2},\dots,u_{t}$. We assume
that for each $i$, $w$ is adjacent to both $u_{i}$ and $v_{i}$; otherwise $w$
is not a usable color for $u_{i}v_{i}$, and ignores that pair. If $t=1$, $w$
broadcasts $u_{1},v_{1}$ to its neighbors, indicating that $u_{1}v_{1}$ is
colored with $w$, otherwise $w$ broadcasts a message indicating that color $w$
was not taken in the given round. All handler nodes update their palettes
accordingly.

It is easy to see that the above correctly simulates RandomColorTrial in $H$
with apparent palettes. A vertex $uv$ is colored in a given round if its
random color lands in $\Psi(v)$ and is different from the colors picked by its
neighbors; hence, if $d_{0},d$ denote the number of uncolored neighbors of
$uv$ at the beginning of the algorithm and in the current round, respectively,
then $uv$ is colored w.p.

$\frac{|\Psi^{\prime}(uv)|-|\Psi^{\prime}(uv)\setminus\Psi(uv)|-d}{|\Psi^{\prime}(uv)|}\geq
1-\frac{d_{0}+d}{|\Psi^{\prime}(uv)|}\geq 1/2\ ,$

where the last inequality follows from the observation that each vertex has
slack $3d_{0}$ (and slack never decreases). Moreover, the probability bound
clearly holds even when conditioned on adversarial candidate color choices of
neighbors. Thus, also using that $\Delta=\Omega(\log^{2}n)$, with a large
enough coefficient, we can apply Chernoff bound (7) to show that while there
are at least $\frac{\varepsilon\Delta}{3\log n}$ uncolored vertices, in each
iteration, the number of uncolored vertices decreases by a constant factor,
w.h.p. (we use the assumption that $\varepsilon\Delta=\Omega(\log^{2}n)$, with
a large enough coefficient); therefore, in $O(\log\log n)$ rounds there are at
most $\frac{\varepsilon\Delta}{3\log n}$ vertices remaining to be colored,
w.h.p. To finish coloring, in one more round, each node $u$ tries $3\log n$
colors in parallel, for each vertex $uv$ it handles. The probability of
success of each trial is at least $1/2$, by the same analysis as above, since
we can view parallel trials by the same vertex as trials by $3\log n$
different vertices; even so, each vertex will have degree bounded by
$2\varepsilon\Delta$, and slack at least three times that, as before. Thus,
each parallel trial for a given vertex succeeds w.p. at least $1/2$,
irrespective of the outcome of other trials (including the trials for other
vertices). Since there are at least $3\log n$ trials per vertex, Chernoff
bound (6) implies that each vertex is successfully colored, w.h.p. ∎

######  Remark 9.10.

In the proof above, the ability of a node $u$ to locally resolve conflicts
between the candidate color picks by the vertices $uv$ it handles makes the
coloring problem more like a $\mathsf{LOCAL}$ coloring, since every vertex can
now try many colors in parallel. This suggests that the multi-trial technique
of [SW10] can be applied to get a $O(\log^{*}n)$ time algorithm. A quicker
improvement can be obtained by using a variant of Lemma 5.2, which, given that
all nodes have equal initial slack $\Omega(\Delta)$, reduces their degrees to
$O(\Delta/\log n)$ in $O(\log\log\log n)$ rounds. Note that we need to use
parallel trials here too, in order to suppress the failure probability caused
by the difference between the apparent and real palettes.

##  10 Coloring Small Degree Graphs

In this section, we show how to $(deg+1)$-list color a graph in
$O(\log\Delta)+\operatorname{poly}\log\log(n)$ rounds. This result is
efficient in the small degree case, i.e., when the maximum degree is bounded
by $\operatorname{poly}\log(n)$, with runtime reducing to $O(\log^{5}\log n)$
rounds. We call the obtained algorithm ColorSmallDegreeNodes.

######  Theorem 10.1.

Let $H$ be a subgraph of $G$ with maximum degree $\Delta_{H}$. Assume that
each node $v$ of degree $d_{v}$ in $H$ has a palette $\Psi(v)\subseteq[U]$ of
size $|\Psi(v)|\geq d_{v}+1$ from a colorspace of size
$U=\operatorname{poly}(n)$. There is a $O(\log\Delta_{H}+\log^{5}\log
n)$-round randomized algorithm that w.h.p. colors $H$ by assigning each node
$v$ a color from its palette.

Similar results are known in the $\mathsf{LOCAL}$ model [BEPS16, RG20, GGR21]
and the $\mathsf{CONGEST}$ model [Gha19, GGR21], where the latter has slightly
worse runtime. We provide a (mostly) self contained proof of the result,
meantime fixing an error in the state-of-the-art $\mathsf{CONGEST}$ algorithm
(see Remark 10.7) and slightly improving the runtime, and thus matching the
runtime of the state-of-the-art in the $\mathsf{LOCAL}$ model. Our algorithm
consists of four steps: _Shattering_ , _Network Decomposition_ , _Colorspace
Reduction_ and _Cluster Coloring_. These four steps have been used in a
similar (but not identical) manner in [Gha19]. Colorspace reduction is an
adaptation of a result in [HKMN20], and the shattering part stems from
[BEPS16].

#### High Level Overview

The _shattering_ part consists of $O(\log\Delta_{H})$ iterations of
RandomColorTrial. This results in a partial coloring of the graph, after which
the uncolored parts of $H$ form connected components of size
$N=\operatorname{poly}\log(n)$, w.h.p., as shown in [BEPS16]. In the remainder
of the algorithm, such components are processed in parallel and independently
from each other.

In the _network decomposition_ part, each component is partitioned into
$\Gamma_{1},\ldots,\Gamma_{c}$ collections of _clusters_ , with $c=O(\log\log
n)$. The important properties of this decomposition are: (i) the clusters in
each $\Gamma_{i}$ are independent, i.e., there is no edge between the nodes of
any two distinct $Q,Q^{\prime}\in\Gamma_{i}$, (ii) each cluster
$Q\in\Gamma_{i}$ _essentially_ has a $\operatorname{poly}\log\log(n)$
diameter. By Property (i), all clusters in $\Gamma_{i}$ can be colored in
parallel without interference, while Property (ii) is used to do that
efficiently.

The algorithm that we use to color the clusters has runtime depending on the
size of the colorspace. In order to make the coloring procedure efficient, we
perform _color reduction_ , where we deterministically compute a function
$f_{Q}$ that maps the color palettes of all nodes in $Q$ to a much smaller
colorspace of size $\operatorname{poly}(N)$, while preserving the palette
sizes. In the new color space, each color can be represented with $O(\log\log
n)$ bits. This step is run on all clusters in all $\Gamma_{i}$ in parallel.

In the _cluster coloring part_ , we iterate through the groups
$\Gamma_{1},\ldots,\Gamma_{c}$. When processing $\Gamma_{i}$ each cluster
$Q\in\Gamma_{i}$ is colored in parallel. Note that we need to solve a
$(deg+1)$-list coloring on $Q$: all colors of previously colored neighbors in
a cluster in $\Gamma_{1},\ldots,\Gamma_{i-1}$ are removed from the palettes of
nodes in $Q$. In the last step, we solve the list coloring problem on $Q$ by
simulating $O(\log n)$ parallel and independent instances of the simplest
coloring algorithm: iterate RandomColorTrial, for $O(\log N)$ rounds; note
that the size of $Q$ is upper bounded by $N=\operatorname{poly}\log(n)$. The
failure probability of each instance is $1/\operatorname{poly}(N)$, and w.h.p.
(in $n$), at least one of these instances is successful [Gha19, Sec. 4]. After
executing all instances for $O(\log N)$ iterations, the nodes in $Q$ agree on
a successful instance and get permanently colored with the colors chosen in
that instance.

The color space reduction is necessary for sending the random color trials of
several parallel instances in one $O(\log n)$-bit $\mathsf{CONGEST}$ message.
Alternatively, one could replace the cluster coloring procedure with the
deterministic $(deg+1)$-list coloring algorithm from [BKM20]. However, its
runtime depends logarithmically on the color space, and one would need the
same color space reduction to obtain a $\operatorname{poly}\log\log(n)$ round
algorithm. The runtime of our approach is dominated by the time to compute a
network decomposition.

#### Shattering

Barenboim, Elkin, Pettie, and Su [BEPS16] showed that $O(\log\Delta_{H})$
rounds are sufficient to reduce the $(deg+1)$-list coloring problem on an
$n$-node graph $H$ to several independent $(deg+1)$-list coloring instances on
subgraphs with $N=\operatorname{poly\log}(n)$ nodes. In the remaining parts,
we focus on handling one such subgraph. Let us detail the algorithm of
[BEPS16], to demonstrate its simplicity (the analysis is nontrivial though).
By [BEPS16, Lemma 5.3], after $O(\log\Delta_{H})$ iterations of
RandomColorTrial in $H$, the maximum size of a connected component of
uncolored nodes in $H$ is $O(\Delta_{H}^{2}\log n)$, w.h.p. One can now
partition the uncolored vertices into two groups (depending on the uncolored
degree) that need to be list-colored one after the other. In one of the
groups, $O(\log\Delta_{H})$ more iterations of RandomColorTrial suffice to
reduce the maximum size of an uncolored connected component to
$N=\operatorname{poly}\log(n)$, while in the other group, uncolored components
are bounded in size by $N$, by design. The analysis is independent of the
colorspace, and this shattering procedure can be executed in
$\mathsf{CONGEST}$. The two groups are processed sequentially, but inside each
group, all uncolored components are colored in parallel. Notice that there are
no conflicts between them, as all communication happens within individual
components. Henceforth, we fix such a component $L$ and describe the coloring
algorithm in $L$. By omitting excess colors, we can also assume that the list
size of each vertex is upper bounded by $d_{L}(v)+1\leq|L|\leq N$.

#### Network decomposition

To color a component $L$, we first compute a _network decomposition_ of $L$,
using a deterministic algorithm from [GGR21]. To highlight that all
(uncolored) components of $G$ are handled in parallel and independently, we
formulate all results in this section from the viewpoint of a graph $L$.

######  Definition 10.2.

A _network decomposition_ of a graph $L$, with weak diameter $d$ and a number
of colors $c$, consists of a partition of $L$ into vertex-induced subgraphs or
_clusters_ $S_{1},\dots,S_{t}$ and a coloring of the clusters with $c$ colors,
such that: 1. For any $i\neq j$, if $S_{i}$ and $S_{j}$ have the same color,
then there is no edge with one endpoint in $S_{i}$ and the other in $S_{j}$,
2. for each $i$ and $u,v\in S_{i}$, the distance from $u$ to $v$ in $L$ is
bounded by $d$.

In a network decomposition with $c$ colors, let $\Gamma_{1},\ldots,\Gamma_{c}$
denote the collection of clusters colored with the colors $1$ to $c$,
respectively.

######  Theorem 10.3.

[GGR21] Let $L$ be $k$-node graph where each node has a $b=\Omega(\log k)$-bit
ID. There is a deterministic algorithm that computes a network decomposition
of $L$ with $O(\log k)$ colors and weak diameter $O(\log^{2}k)$, in
$O(\log^{5}k+(\log^{*}b)\log^{4}k)$ rounds of the $\mathsf{CONGEST}$ model
with $b$-bit messages. Moreover, for each cluster $Q$, there is a Steiner tree
$T_{Q}$ with radius $O(\log^{2}k)$ in $L$, for which the set of terminal nodes
is $Q$. Each vertex of $L$ is in $O(\log k)$ Steiner trees of each color.

Aggregation procedures can be efficiently pipelined in the computed network
decomposition.

######  Lemma 10.4 ((simplified), [GGR21]).

Let $L$ be a communication graph on n vertices. Suppose that each vertex of
$L$ is part of some cluster $Q$ such that each such cluster has a rooted
Steiner tree $T_{Q}$ of diameter at most $R$ and each node of $L$ is contained
in at most $P$ such trees. Then, in $O(P+R)$ rounds of the $\mathsf{CONGEST}$
model with $b$-bit messages for $b\geq P$, we can perform the following
operations for all clusters in parallel: broadcast, convergecast, minimum,
summation and bit-wise maximum.

For the precise definition of broadcast, convergecast, minimum and summation,
we refer to [GGR21]. In the _bit-wise maximum_ of a cluster $Q$, each vertex
$v\in Q$ has a bit string of $\ell=O(b)$ bits $s_{1}(v),\ldots,s_{\ell}(v)$,
and we say $Q$ computes the bit-wise maximum if a designated leader node in
$Q$ knows the bit string $s_{1},\ldots,s_{\ell}$, where $s_{i}=\max_{v\in
Q}s_{i}(v)$. While the computation of bit-wise maximum is not explicitly
mentioned in [GGR21], it follows from their claim that a function $\circ$ can
be computed in the claimed runtime if it is associative and
$p_{i}(x_{1}\circ\dots\circ x_{k})$ can be computed from
$p_{i}(x_{1}),\ldots,p_{i}(x_{k})$ where $p_{i}$ denotes the $i$ leftmost (or
rightmost) bits of a string. Both properties clearly hold for the bit-wise
maximum.

We apply Theorem 10.3 to each component $L$. Since $L$ has size $O(\log^{3}n)$
and IDs of size $O(n)$, we obtain a network decomposition with $O(\log\log n)$
colors and weak diameter $O(\log^{2}\log n)$, in $O(\log^{5}\log n)$ time, and
each vertex is in at most $O(\log\log n)$ Steiner trees of each color.

#### Colorspace Reduction

We map the colorspace $[U]$ to a smaller colorspace that is comparable to the
size $N$ of an uncolored component. This is described in the following lemma,
which is a reformulation of a similar lemma from [HKMN20].

######  Lemma 10.5.

Let $N>\log n$ be an upper bound on the number of vertices and the diameter of
some subgraph $H$ of a connected communication network $G$. Let the list of
each node $v$ have size $|\Psi(v)|\leq N$, and the colorspace have size
$U=\operatorname{poly}(n)$. There is a constant $c_{0}>0$ such that all
vertices of $H$ learn the same mapping $f:[U]\to[N^{c_{0}}]$ s.t. for each
vertex $v\in H^{\prime}$, $|f(\Psi(v))|=|\Psi(v)|$, by executing $O(\log N)$
iterative summation and broadcast primitives in $H$.

###### Proof.

Let the constant $c_{0}>0$ be such that $(N^{c_{0}}/2)^{N^{c_{0}-5}/2}>U$.
Such a constant exists, since $U=\operatorname{poly}(n)$ and $N>\log n$. Let
$N^{c_{0}}/2<p\leq N^{c_{0}}$ be a prime, which exists due to Bertrand’s
postulate. The reduction is given by a random hash function, which is then
derandomized using the method of conditional expectation. We start by
describing this in the centralized setting, and then comment on how to do it
distributively.

Let $d=\lceil p/N^{5}\rceil$. To each color $\alpha\in[U]$, we assign a unique
polynomial $\psi_{\alpha}\in\mathbb{F}_{p}[x]$ of degree $d$. This can be done
since the number of degree-$d$ polynomials over $\mathbb{F}_{p}$ is
$p^{d+1}>(N^{c_{0}}/2)^{N^{c_{0}-5}/2}>C$.

To obtain the color reduction $f:[U]\to[N^{c_{0}}]$ we want to choose a “good”
function from the set $\\{f_{g}:g\in\mathbb{F}_{p}\\}$, where

$f_{g}:[U]\rightarrow\mathbb{F}_{p}\text{, and
}f_{g}(\alpha)=\psi_{\alpha}(g).$

In other words, we fix a distinct polynomial $\psi_{\alpha}$ for each color
$\alpha\in[U]$ and for each $g\in\mathbb{F}$ we obtain a ’candidate color
reduction’ $f_{g}$ by mapping color $\alpha\in[U]$ to the evaluation of its
polynomial $\psi_{\alpha}$ at $g$. The function $f_{g}$ is _good_ if it
preserves the list sizes of all nodes $u$ of $H$: For each node $u$ and
$g\in\mathbb{F}_{p}$, let $X_{u}(g)$ be 0 if $|f_{g}(\Psi(u))|=|\Psi(u)|$, and
1, otherwise. A function $f_{g}$ is _good_ if $\sum_{u\in H}X_{g}(u)=0$; the
latter implies that for each node $u$, $|f_{g}(\Psi(u))|=|\Psi(u)|$, as
required.

First, let us show that a random function $f_{g}$, corresponding to a
uniformly random choice of $g$ is good with significant probability.

######  Claim 1.

If $g\in\mathbb{F}_{p}$ is chosen uniformly at random, then
$\mathbb{E}\big{[}\sum_{u\in H}X_{u}\big{]}\leq N^{-2}$.

###### Proof.

Consider a node $u$. For two distinct colors $\alpha,\beta\in\Psi(u)$, the
polynomials $\psi_{\alpha}$ and $\psi_{\beta}$ intersect in at most $d$
points; hence, if $g$ is sampled uniformly, the probability that
$f_{g}(\alpha)=\psi_{\alpha}(g)=\psi_{\beta}(g)=f_{g}(\beta)$ is $d/p\geq
N^{-5}$. Thus, the probability that any two colors in $\Psi(u)$ map to the
same element of $\mathbb{F}_{p}$ is at most $\binom{|\Psi(u)|}{2}\cdot
d/p<N^{2}\cdot N^{-5}=N^{-3}$. The claim follows by linearity of expectation,
since the sum is over at most $N$ elements, each having expectation at most
$N^{-3}$. $\hfill\blacksquare$

We assume that the elements of $\mathbb{F}_{p}$ are numbered from 1 to $p$ and
we choose the element $g$ by choosing its bits independently: we flip
$\ell=\lceil\log_{2}p\rceil$ unbiased coins, $b_{1},\dots,b_{\ell}$, and let
$g$ be the number with the binary representation $b_{1}\dots b_{\ell}$. Let
$Y$ be a binary random variable that is 1 if $g>p$, and 0, otherwise.
Conditioned on $Y=1$, $g$ is uniformly distributed in $\mathbb{F}_{p}$. Let us
re-define $X_{u}(g)$ to be 0 also when $g>p$. Note that we still have
$\mathbb{E}[\sum_{u\in H}X_{u}]=\mathbb{E}[\sum_{u\in H}X_{u}\mid
Y=1]\Pr[Y=1]\leq 1/N^{2}$, since we only make $X_{u}$ smaller in some cases.
We also have $\mathbb{E}[Y]\leq 1/2$; hence, assuming $N\geq 3$,

$\mathbb{E}\left[Y+\sum_{u\in H}X_{u}(g)\right]\leq 1/2+1/N^{2}\leq 2/3\ .$
(5)

In order to find a good function $f_{g}$, it suffices to find $b_{1}\dots
b_{\ell}$ such that $Y+\sum_{u\in H}X_{u}<1$. In order to derandomize (5), we
fix the bits $b_{1},\dots,b_{\ell}$ inductively, with the basis (5). Given
$b_{1},\dots,b_{i}\in\\{0,1\\}$, for $i\geq 0$, such that
$\mathbb{E}[Y+\sum_{u\in H}X_{u}(g)\mid b_{1},\dots,b_{i}]\leq 2/3$, we select
$b_{i+1}\in\\{0,1\\}$ such that $\mathbb{E}[Y+\sum_{u\in H}X_{u}(g)\mid
b_{1},\dots,b_{i},b_{i+1}]\leq 2/3$. The existence of such a value follows
from the inductive hypothesis, using the conditional expectation formula
(conditioning on $b_{i+1}$). After fixing all bits, we have a deterministic
value $g$ for which $Y+\sum_{u\in H}X_{u}(g)\leq 2/3$.

It remains to see how to compute a good function distributively. We do this in
$\ell$ phases, where we fix $b_{i}$ in phase $i$, assuming the bits
$b_{1},\dots,b_{i-1}$ have been fixed, and each node knows those bits. To this
end, each node computes $\mathbb{E}[X_{u}\mid b_{1},\dots,b_{i-1},0]$ and
$\mathbb{E}[X_{u}\mid b_{1},\dots,b_{i-1},1]$, with precision $N^{-5}$. Note
that such values fit in a single message of size $O(\log n)$. These values are
aggregated in a leader node, i.e., a leader node learns values
$v_{b}=\mathbb{E}\left[\sum_{u\in H}X_{u}\mid b_{1},\dots,b_{i-1},b\right]\pm
N^{-4}$, for $b=0,1$, and computes
$v_{b}^{\prime}=\mathbb{E}\left[Y+\sum_{u\in H}X_{u}\mid
b_{1},\dots,b_{i-1},b\right]\pm N^{-4}$, and chooses $b_{i}=b$ such that
$v_{b}^{\prime}\leq v^{\prime}_{1-b}$. The overall error accumulated
throughout the $\ell$ phases is at most $\ell N^{-4}\leq N^{-3}$. This,
implies that when all $\ell$ bits are fixed, we have $Y+\sum_{u\in
H}X_{u}<2/3+N^{-3}<1$; hence, the computed function is good. It takes
$O(\ell)=O(\log N)$ summation and broadcast operations to compute the color
reduction. $\Box$

To obtain a color space reduction, i.e., a function $f_{Q}$, for each cluster
$Q$ of the network decomposition, that maintains the list sizes, we apply the
algorithm from Lemma 10.5 to all clusters in all
$\Gamma_{1},\ldots,\Gamma_{c}$ in parallel. Since we run it on $O(\log\log n)$
color classes in parallel, and a node can be in $O(\log\log n)$ Steiner trees
per color class, a node can be in $P=O(\log^{2}\log n)$ Steiner trees of all
clusters. Using Lemma 10.4, the $O(\log N)=O(\log\log n)$ iterative summation
and broadcast primitives of Lemma 10.5 can be implemented in the Steiner trees
of diameter at most $D=O(\log^{2}\log n)$ in $O(\log
N\cdot(D+P))=O(\log^{3}\log n)$ rounds.

#### Cluster Coloring (by [Gha19])

Algorithm 8 Cluster Coloring

1: Given: network decomposition $\Gamma_{1},\ldots,\Gamma_{c}$, color space
reduction $f_{Q}$, for each cluster $Q$

2: for $i=1,\dots,c$ do

3: for all clusters $Q\in\Gamma_{i}$ in parallel do

4: Update palettes: Remove colors used by permanently colored neighbors (in
$G$)

5: Map lists: Use $f_{Q}:[U]\rightarrow[N^{c_{0}}]$ to map remaining lists to
a smaller color space

6: for $O(\log N)=O(\log\log n)$ iterations and $O(\log n)$ parallel instances
do

7: Simulate RandomColorTrial

8: Agree on a successful instance and permanently color each node in $Q$

While the update of the lists takes place in the original color space, the
simultaneous instances of RandomColorTrial work in a smaller color space of
size $\operatorname{poly}(N)$, and each of its colors can be represented with
$O(\log N)=O(\log\log n)$ bits. In fact, the color trials of one round of
$O(\log n)$ instances use $O(\log n\cdot\log\log n)$ bits and can be done in
$O(\log\log n)$ rounds. Thus, the $O(\log N)=O(\log\log n)$ rounds in total
can be simulated in $O(\log^{2}\log n)$ rounds. Each of these instances is
successful with probability $1/\operatorname{poly}(N)$ and w.h.p. (in $n$), at
least one of them is successful [Gha19, Sec. 4]. A node can locally determine
which instances are successful, i.e., in which instances it gets colored. For
node $v$, let $s_{1}(v)\cdots s_{\ell}(v)$ be the indicator string in which
$s_{i}(v)$ indicates whether instance $i$ was successful for node $v$. With a
bit-wise maximum, a leader can determine an instance that is successful
w.h.p., for all nodes in the cluster, and can broadcast it to all nodes.
Updating lists and applying the color space reduction can be done in one
round, simulating the instances takes $O(\log^{2}\log n)$ rounds, and agreeing
on a successful instance takes $O(\log^{2}\log n)$ rounds, due to the diameter
of the Steiner trees and Lemma 10.4. Thus, the total runtime by iterating over
all color classes of the network decomposition is $O(\log^{3}\log n)$.

###### Proof of Theorem 10.1.

By design, after executing all four steps, all nodes of the graph are properly
colored. The shattering part takes $O(\log\Delta_{H})=O(\log\log n)$ rounds.
Computing the network decomposition takes $O(\log^{5}\log n)$ rounds. The
color space reduction runs on all clusters in parallel and takes
$O(\log^{3}\log n)$ rounds. The cluster coloring part takes $O(\log^{2}\log
n)$ rounds per color class of the network decomposition and $O(\log^{3}\log
n)$ rounds in total. ∎

######  Remark 10.6.

A slightly worse runtime of $O(\log^{6}\log n)$ rounds can be obtained by
using the algorithm of [BKM20] to list color the clusters. Without the
pipelining (Lemma 10.4) to speed up aggregation within clusters the runtime
gets even slower but it remains $\operatorname{poly}\log\log(n)$.

######  Remark 10.7.

The high level structure of the algorithm for Theorem 10.1 is similar to the
one in [Gha19], using the updated intermediate procedures to compute a network
decomposition from [GGR21] and the color reduction from [HKMN20].

Unfortunately, the $O(\log\Delta)+2^{O(\log\log n)}$ algorithm in [Gha19] has
a mistake in the design of its color space reduction. To reduce the color
space [Gha19] maps the original color lists to a smaller color space $[p]$
where $p$ is a fixed (and deterministically chosen) prime in $[N^{4},2N^{4}]$.
Color $x$ is mapped to $h_{a,b}(x)=a\cdot x+b\bmod p$ with randomly chosen $a$