Distributed $(Δ+1)$-Coloring in $O(\sqrtΔ+\log^* n)$ Rounds

Distributed (∆ + 1)-Coloring in √ O( ∆ + log∗ n) Rounds Marc Fuchs

· marc.fuchs@cs.uni-freiburg.de · University of Freiburg

Fabian Kuhn

· kuhn@cs.uni-freiburg.de · University of Freiburg

arXiv:2610.16575v1 [cs.DS] 12 Oct 2026

Abstract We give a deterministic √ distributed algorithm for (∆ + 1)-coloring an n-node graph of maximum degree ∆ in O( ∆+log∗ n) rounds in both the LOCAL and CONGEST models. More generally, √ (deg +1)-list coloring with lists from a color space of size C ≥ ∆ + 1 can be solved in O( ∆ log(1 + C/∆) + log∗ n) rounds; in CONGEST, we assume C ≤ nO(1) . The algorithm combines Barenboim’s polynomial coloring procedure with arbdefective decompositions, degree reduction, and a short family of hash functions. √ Using the polynomial procedure in the degree-reduction framework already gives an O( ∆ log ∆ + log∗ n)-round algorithm when C = O(∆). Hashing adapts the color space to the current degree and removes the logarithmic factor. We prove the existence of the hash family by the probabilistic method and compute it by deterministic exhaustive search, using unrestricted local computation. We also√give an explicit variant based on lossless expanders that avoids this search and achieves O( ∆ + log∗ n) rounds for C = O(∆).

Contents 1 Introduction and Related Work 1.1 Our Main Contribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Previous Sublinear-in-∆ Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Combining Barenboim’s Algorithm with Degree Reduction . . . . . . . . . . . . . . . . . . 1.4 Reducing the Color Space by Hashing . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1 2 3 4 4

2 Model and Preliminaries 2.1 Basic Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Computing Auxiliary and Arbdefective Colorings . . . . . . . . . . . . . . . . . . . . . . . 2.3 Polynomials over Finite Fields . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5 5 5 6

3 The New Coloring Algorithm 3.1 Basic Algebraic List Coloring with Bounded Outdegree . . . . . . . . . . . . . . . . . . . 3.2 Degree Reduction without Hashing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3 A Short Family of Hash Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4 Coloring with Compressed Color Spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6 6 8 10 11

AI Disclosure

12

References

13

A Explicit Hash Functions A.1 From Lossless Expanders to Hash Functions . . . . . . . . . . . . . . . . . . . . . . . . . . A.2 The Coloring Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

15 15 16

1

Introduction and Related Work

Distributed graph coloring is one of the core problems in the area of distributed graph algorithms and, more generally, in distributed computing. In the standard setting, the network is modeled as an n-node graph G = (V, E), and the objective is to compute a proper coloring of the nodes of G. If the maximum degree of G is ∆, the most common task is to color G with ∆ + 1 colors, matching the guarantee of a simple sequential greedy algorithm. The problem is usually studied in a synchronous message-passing model [22, 27]. Each node has a unique O(log n)-bit identifier and initially knows only its own identifier, its incident communication links, its local input, and any explicitly assumed global parameters. In each round, every node can send a message to each of its neighbors, receive their messages, and perform local computations. At the end, each node must know its own color. The time complexity is the number of rounds until all nodes terminate. Without a restriction on message sizes, this is the LOCAL model; restricting each message to O(log n) bits gives the CONGEST model. In both models, local computation is unrestricted. There are two natural ways to study the complexity of distributed coloring: as a function of the number n of nodes and as a function of the maximum degree ∆. When considering the complexity as a function of ∆, the dependence on n is restricted to an additive O(log∗ n) term. This dependence on n is optimal even for 3-coloring a cycle (i.e., even for ∆ = 2), as was shown by Linial [22] for deterministic algorithms and by Naor [25] for randomized algorithms. Concentrating on these two complexity regimes is motivated, in particular, by the gap theorem of Chang, Kopelowitz, and Pettie [8]. For locally checkable labeling (LCL) problems on boundeddegree graphs in the LOCAL model, every deterministic o(log n)-round algorithm can be sped up to run in O(log∗ n) rounds. Moreover, a randomized o(log log n)-round algorithm that succeeds with high probability implies a deterministic O(log∗ n)-round algorithm. Thus, for problems such as (∆ + 1)-coloring, which belong to this fast class for every constant ∆, the dependence on ∆ is a central part of the complexity question. In this paper, we focus on the dependence on ∆. In this context, we also consider the more general (deg +1)-list-coloring problem, where each node v is given a list Lv of at least degG (v) + 1 available colors as input and has to choose its color from Lv so that the resulting coloring is proper. This problem can also be solved by a simple sequential greedy algorithm. Moreover, it arises naturally when computing a (∆ + 1)-coloring in stages, where in each stage some uncolored nodes become colored. When extending a partial coloring, removing the colors of already colored neighbors leaves every uncolored node v with a list of still available colors whose size is at least the number of its uncolored neighbors plus one. Before discussing the complexity as a function of ∆, we briefly review what is known as a function of n. For a long time, √ the best known deterministic and randomized bounds for (∆ + 1)coloring in LOCAL were 2O( log n) and O(log n), respectively. The deterministic bound was based on the network decomposition algorithm of Panconesi and Srinivasan [26], and the randomized bound follows from repeated randomized color trials [19] or from a reduction to Luby’s maximal independent set (MIS) algorithm [23]. Improving these bounds was a longstanding open problem. The first poly(log n)-round deterministic algorithm was given by Rozhoň and Ghaffari [28] as a consequence of their breakthrough work on deterministic network decompositions. The first randomized o(log n)-round algorithm was obtained by Harris, Schneider, and Su [18]. The best known deterministic and randomized upper bounds for (∆ + 1)-coloring in LOCAL 5/3 5/3 e e e are O(log n) and O(log log n), respectively. Here and throughout, O(x) hides factors at most polylogarithmic in x. The deterministic bound follows from the MIS algorithm of Ghaffari and Grunau [12]. The randomized bound combines this result with the shattering algorithm of Chang, Li, and Pettie [7]. In CONGEST, the corresponding bounds are O(log2 ∆ · log n) [13] and O(log3 log n) [17], using deterministic local rounding and communication-efficient randomized coloring, respectively. The n-dependent LOCAL bounds also extend to the more general (deg +1)list-coloring problem. The deterministic bound already holds for this problem [12], and the

1

randomized bound follows by combining it with the algorithm of Halldórsson, Kuhn, Nolin, and Tonoyan [16]. In CONGEST, the deterministic O(log2 ∆ · log n) bound extends to lists from a color space of size at most poly(∆) [13]. For a color space of size at most poly(n), the randomized algorithm of Halldórsson, Nolin, and Tonoyan [17], combined with the network decomposition 3 e of Ghaffari et al. [14], solves (deg +1)-list coloring in O(log log n) rounds. These randomized bounds hold with high probability. The development of deterministic algorithms with an optimal O(log∗ n) dependence on n started with Linial’s O(log∗ n)-round O(∆2 )-coloring algorithm [22] and with the O(∆2 + log∗ n)round (∆ + 1)-coloring algorithm of Goldberg, Plotkin, and Shannon [15]. Together with repeated applications of a simple one-round color reduction, Linial’s algorithm gives a (∆ + 1)-coloring in O(∆ log ∆ + log∗ n) rounds [21, 29]. Barenboim and Elkin, and independently Kuhn, reduced this to O(∆ + log∗ n) [2, 4, 20]. These papers introduced defective coloring as a tool for distributed symmetry breaking. In a d-defective coloring, each node has at most d neighbors with the same color. Many subsequent deterministic distributed coloring algorithms use some form of defective coloring as a subroutine. The first algorithm for (∆ + 1)-coloring with a sublinear dependence on e 3/4 ) + O(log∗ n) ∆ was obtained by Barenboim [1]. He√obtained a (∆ + 1)-coloring in time O(∆ ∗ e ∆) + O(log n). Barenboim’s algorithms also work in the and a (1 + o(1))∆-coloring in time O( CONGEST model. Fraigniaud, Heinrich, and Kosowski [9] subsequently extended Barenboim’s √ e ∆) + O(log∗ n) in LOCAL. framework and improved the bound for (∆ + 1)-coloring to O( Subsequent improvements to the decomposition and list-coloring steps led to the bound p
O ∆ log ∆ + log∗ n for (deg +1)-list coloring in LOCAL when the color space has size at most 2poly(∆) [5, 9, 24]. The bandwidth restriction is relevant for these algorithms. The fast local conflict-coloring routines communicate descriptions √ of sets that can be much larger than O(log n) bits. Fuchs and e ∆) + O(log∗ n)-round CONGEST algorithm for (∆ + 1)-coloring, Kuhn [10] obtained the first O( based on list defective coloring. For (deg +1)-list coloring with a color space of size O(∆) (and thus in particular for the standard (∆ + 1)-coloring problem), their bound is √
O ∆ log2 ∆ log6 log ∆ + log∗ n . Their subsequent work builds on the two-sweep framework of Barenboim √ and Elkin [2] to give a e ∆)+O(log∗ n)-round conceptually simpler list defective coloring algorithm and an alternative O( CONGEST algorithm [11].

1.1

Our Main Contribution

One of the main open questions in the context of local distributed graph √ algorithms is whether one can improve the deterministic ∆-complexity of (∆ + 1)-coloring to o( ∆), while retaining an additive O(log∗ n) term. The above bounds, however, also leave a more immediate open question: can we remove√the remaining polylogarithmic factors in the ∆-complexity of (∆ + 1)-coloring and obtain O( ∆ + log∗ n) rounds in both the LOCAL and CONGEST models? As our main contribution, we answer this question in the affirmative. More generally, we prove the following result. Theorem 1.1. The (deg +1)-list-coloring problem on n-node graphs of maximum degree ∆ can be solved deterministically in     √ C ∗ O ∆ · log 1 + + log n ∆ rounds in the LOCAL model, where C ≥ ∆ + 1 is the size of the color space. The same bound holds in the CONGEST model if C ≤ poly(n). For C = O(∆) √ (and thus in particular for the standard (∆ + 1)-coloring problem), the round complexity is O( ∆ + log∗ n). 2

In the following, we describe the main ideas that lead to Theorem 1.1. We start by discussing the previous sublinear-in-∆ algorithms in more detail.

1.2

Previous Sublinear-in-∆ Algorithms

The sublinear-in-∆ algorithms discussed above build on the framework introduced by Barenboim [1]. As a first step, the algorithm partitions the graph into node-disjoint subgraphs, each with an orientation of small maximum outdegree. For this, it uses arbdefective colorings, which were introduced by Barenboim and Elkin [3]. A β-arbdefective coloring partitions the nodes into color classes, each inducing a graph of arboricity at most β. The arbdefective coloring algorithm of [1] computes such a partition into O((∆/β) polylog ∆) parts in O((∆/β) polylog ∆ + log∗ n) rounds. It also provides each part with an orientation of maximum outdegree at most β. Starting with an uncolored graph, the algorithm colors the O((∆/β) polylog ∆) parts sequentially, extending the existing partial coloring at each step. Coloring each part requires solving a list-coloring problem: each node must choose a color not already used by a colored neighbor. The key ingredient of Barenboim’s algorithm, and of the subsequent algorithms, is a fast list-coloring algorithm for graphs with small outdegree, provided that the nodes have sufficiently large lists. We describe Barenboim’s list-coloring procedure in detail because it is also the basis of our algorithm. The procedure uses polynomials over a finite field.1 Using the outdegree version of Linial’s color reduction (see Section 2.3 of the full version of [24]), we compute, in parallel on the oriented parts, a proper auxiliary (ηβ)2 -coloring of each part in O(log∗ n) rounds, for a suitable constant η > 0. For the list-coloring instance on one of the outdegree-β parts, assume that every list Lv consists of colors from {1, . . . , C}. We choose a finite field Fq with q ≥ ηβ and q 2 ≥ C, and identify the C colors with distinct pairs in F2q . Each node v also encodes its auxiliary color as a pair (av , bv ) ∈ F2q and considers the polynomials2 pv (x) = av x2 + bv x + cv for all cv ∈ Fq . The q sets {(x, pv (x)) : x ∈ Fq } obtained by varying cv partition F2q . Node v chooses cv to maximize the number of colors from its current list Lv in {(x, pv (x)) : x ∈ Fq }. This set therefore contains at least |Lv |/q available colors. Adjacent nodes have distinct polynomials because their auxiliary colors differ. The associated sets therefore share at most two elements: the difference of two distinct polynomials of degree at most two has at most two roots. Thus, if |Lv | > 2qβ, node v can choose an available color from its set that belongs to none of the sets chosen by its at most β outneighbors. Exchanging the polynomials and announcing the chosen colors takes O(1) rounds per part. √ √ For C = Θ(∆) and β = O( ∆), we can choose q = Θ( ∆), so lists larger than a suitable √ constant times β ∆ suffice. With (1 + ε)∆ colors, every node always has at least ε∆ available √ colors. Choosing β = Θ(ε ∆) with a sufficiently small constant therefore gives an algorithm √ ∗ e running in O( ∆) + O(log n) rounds for any fixed ε > 0. To √ obtain a (∆ + 1)-coloring, Barenboim’s algorithm first computes a proper coloring with ∆ + Θ(β ∆) colors. It then recolors the nodes in the extra color classes using the first √ ∆ + 1 colors, one class per round. Balancing the number ∆/β of parts against the number β ∆ of extra colors, up to polylogarithmic factors, gives β = Θ(∆1/4 ). This yields a deterministic (∆ + 1)-coloring algorithm with round complexity e 3/4 ) + O(log∗ n). Barenboim’s algorithm also works in CONGEST, since the polynomials of O(∆ degree at most two can be described with O(log q) = O(log n) bits. Fraigniaud, Heinrich, and Kosowski [9] extended the framework in two ways. They introduced a generalization of ordinary list coloring called conflict coloring and gave a fast algorithm for solving it in graphs with an outdegree-β orientation. For sufficiently large β, their list-coloring subroutine requires O(log∗ ∆) LOCAL rounds when given a proper auxiliary O(∆2 )-coloring and lists of size at least 10β 2 ln ∆. These bounds are independent of the color-space size C. Their 1

Barenboim [1] presents the procedure as extending a partial C-coloring, with colors already used by neighbors treated as forbidden colors. We state it directly for lists of available colors from {1, . . . , C}, which is equivalent. 2 This construction extends to polynomials of any fixed degree r. We later use this generalization with r = 4; see Section 3.1.

3

second extension concerns how the parts are processed. Instead of fully coloring all parts in one pass, they color only nodes with sufficiently large remaining lists and choose β so that each pass halves the maximum uncolored √ degree. The algorithm then recurses on the remaining graph. Overall, this results in an O( ∆ log5/2 ∆ + log∗ n)-round (deg +1)-list-coloring algorithm. The bound was later improved in two steps. Barenboim, Elkin, and Goldenberg [5] improved the arbdefective coloring algorithm to obtain a decomposition into O(∆/β) parts, each with an orientation of maximum outdegree computable in O(∆/β + log∗ n) rounds. This √ at most β, reduces the overall bound to O( ∆ log ∆ log∗ ∆ + log∗ n). Maus and Tonoyan [24] then gave a two-round list-coloring subroutine for outdegree-β graphs with the same auxiliary coloring, lists of size Ω(β 2 log ∆) with a sufficiently large constant, and a color space of√size C ≤ 2poly(∆) . This removes the log∗ ∆ factor, giving the best previous LOCAL bound of O( ∆ log ∆ + log∗ n) rounds for (deg +1)-list coloring and standard (∆ + 1)-coloring. The large messages used by these list-coloring procedures prevent a direct implementation in CONGEST. Fuchs and Kuhn [10] overcame this by combining a list version of defective coloring with color-space reduction. This allows the bounded-outdegree parts to be colored in several steps, each using a limited number √ of colors and thus smaller messages. They obtained a CONGEST e ∆) + O(log∗ n) rounds for (deg +1)-list coloring when C ≤ poly(∆). algorithm running in O( √ For C = O(∆), the bound is O( ∆ log2 ∆ log6 log ∆ + log∗ n).

1.3

Combining Barenboim’s Algorithm with Degree Reduction

We now describe the main ideas that lead to our improved bounds. Our first observation is that Barenboim’s algorithm [1], described above, can be used directly in the degree-reduction framework of Fraigniaud, Heinrich, and Kosowski [9]. The framework colors the graph in stages, each halving a bound on the maximum degree of the uncolored subgraph. Assume we still need to color a graph of maximum degree at most ∆′ ≤ ∆. Our goal is to extend the partial coloring so that the maximum degree of the uncolored subgraph becomes at most ∆′ /2. Note that an uncolored node with at least ∆′ /2 uncolored neighbors also has at least ∆′ /2 available colors. Recall that, given a suitable auxiliary coloring, √ Barenboim’s procedure colors outdegree-β graphs in constant time if the lists have size Ω(β C), long √ with a sufficiently large constant. As √ as ∆′ exceeds a sufficiently large constant multiple of C, we can therefore choose β = Θ(∆′ / C) so that lists of size ∆′ /2 suffice. The decomposition of Barenboim, Elkin, and Goldenberg [5] √ then gives O(∆′ /β) = O( C) parts. We process these parts sequentially, coloring only nodes with at least ∆′ /2 currently available colors. Every node left uncolored then has fewer than ∆′ /2 ′ available colors √ and hence fewer than ∆ /2 uncolored neighbors. Thus, a stage halves the degree bound in O( C) rounds. For C = O(∆), repeating these √ stages O(log ∆) √ times and using a simple finishing procedure once the remaining degree is O( ∆) gives an O( ∆ log ∆ + log∗ n)-round algorithm. It works in CONGEST and already improves on the previous bound in that model. We can improve this further by stopping after O(log log ∆) stages, when the maximum uncolored degree is at most ∆/ loga ∆ √ for a sufficiently large constant a. An existing list-coloring algorithm in O( ∆ + log∗ n) rounds. Thus, this combination alone gives √ [10, 24] then finishes ∗ an O( ∆ log log ∆ + log n)-round algorithm in both LOCAL and CONGEST, improving on the previous LOCAL bound as well.

1.4

Reducing the Color Space by Hashing

√ In the approach above, each degree-halving stage takes O( C) rounds: Barenboim’s procedure still uses the original color space, even as the degree decreases. To make later stages faster, we use hashing to shrink the color space along with the degree. For the current degree bound ∆′ , set k = ∆′ /2. We use a common sequence of O(log(1+C/k)) hash functions from [C] to a color space of size O(k) such that every list of at least k colors has 4

more than √ k/2 distinct images under √ at least one function. We partition the uncolored graph into O( ∆′ ) parts of outdegree O( ∆′ ) and process the parts sequentially. Within each part, we try all hash functions in order, using Barenboim’s procedure to color nodes whose image lists have more than k/2 colors. All active nodes in a call use the same function, so choosing preimages from their available lists preserves properness. If a node remained uncolored with at least k available colors, some function would preserve more than k/2 images of its final list. Since lists only shrink, that function would have allowed us to color the node when it was tried in the node’s part. Thus, every remaining list has fewer than k colors, and hence every uncolored node has fewer than k = ∆′ /2 uncolored √ neighbors. Trying ′ all functions in one part takes O(log(1√+ C/∆ )) rounds. Processing all O( ∆′ ) parts, including the partition computation, takes O( ∆′ log(1 + C/∆′ ) + log∗ ∆) rounds per stage. Summing over the degree scales gives Theorem 1.1. We prove the existence of the hash family by the probabilistic method. All nodes can find the same family by deterministic exhaustive search, since local computation is unrestricted. In Appendix A, we give an alternative based on explicit lossless expanders that avoids this search. It 3 replaces the factor log(1 + C/∆) in the round complexity by 2O((log log(4+C/∆)) ) , while retaining √ O( ∆ + log∗ n) rounds for C = O(∆).

2

Model and Preliminaries

2.1

Basic Definitions

We use the synchronous LOCAL and CONGEST models described in Section 1. All graphs are finite, simple, and undirected. As part of our algorithm, we compute edge orientations, which are used to assign responsibility for avoiding color conflicts. When we work with oriented graphs, communication remains possible in both directions on every edge. Orientations need not be + acyclic. We write NH (v) for the neighbors of v in a graph H, and NH (v) for its outneighbors in an oriented graph. We omit the subscript when the graph is clear. For an integer a ≥ 1, we write [a] = {1, . . . , a}. In our list-coloring instances, the color lists are subsets of [C], and we assume that all nodes know ∆ and C. In CONGEST, we assume C ≤ nO(1) . We assume ∆ ≥ 2, since the case ∆ ≤ 1 can be solved in one round. All logarithms are binary. The iterated logarithm log∗ x is the minimum number of successive applications of the logarithm needed to reduce x to at most one. In asymptotic bounds, we take all logarithms and iterated logarithms to be at least one.

2.2

Computing Auxiliary and Arbdefective Colorings

We distinguish the colors chosen from the input lists from auxiliary colors used for symmetry breaking and scheduling. The following standard form of Linial’s color reduction will be useful. Theorem 2.1 (Color reduction [22]). There is an absolute constant κ such that a graph of maximum degree at most ∆ ≥ 1, equipped with a proper γ-coloring, can be properly colored with at most κ∆2 colors in O(log∗ γ) rounds. The algorithm works in CONGEST when γ ≤ nO(1) . In particular, unique identifiers give a proper O(∆2 )-coloring in O(log∗ n) rounds. A β-arbdefective p-coloring is a partition into p color classes such that each class induces a graph of arboricity at most β, where arboricity is the minimum number of forests needed to cover the edges. We use the oriented version: together with the partition, the algorithm supplies an orientation of each induced subgraph with maximum outdegree at most β. Such an orientation implies arboricity at most β + 1; conversely, a graph of arboricity at most β has an orientation of outdegree at most β. These constant differences are immaterial for our applications. We state the required decomposition directly in terms of outdegree. 5

Theorem 2.2 (Arbdefective decomposition [5, 24]). Given a graph of maximum degree at most ∆, a proper γ-coloring, and an integer 1 ≤ β ≤ ∆, one can compute a partition V = V1 ∪˙ · · · ∪˙ Vp ,

p = O(∆/β),

and an orientation of each G[Vi ] of maximum outdegree at most β, in O(∆/β+log∗ γ) deterministic CONGEST rounds. For β above an absolute constant, this is the formulation of the result of Barenboim, Elkin, and Goldenberg given in Lemma 4.1 of the full version of Maus and Tonoyan [24]. For smaller positive β, compute a proper O(∆)-coloring in O(∆+log∗ γ) CONGEST rounds using Theorem 2.1 followed by the color reduction of [5]. Its independent color classes have outdegree zero, and O(∆) = O(∆/β) in this case. The stated bound also covers one round to inform both endpoints of the part memberships and edge orientations. Part indices are taken from a commonly known range of size O(∆/β), so processing the parts does not require finding the largest index actually used. Restricting a part to a subset of its nodes preserves the outdegree bound.

2.3

Polynomials over Finite Fields

For every real x ≥ 2, a power of two q can be chosen with x ≤ q < 2x, and a field Fq exists. We use a fixed representation of this field known to all nodes. For a polynomial P ∈ Fq [X], let ΓP := {(x, P (x)) : x ∈ Fq }

(1)

be its graph. The following lemma collects the properties used in the algebraic list-coloring primitive. Lemma 2.3 (Polynomial partitions). Let q be a prime power and r ≥ 1 an integer. There are q r polynomials over Fq with zero constant coefficient and degree at most r. For each such polynomial P , the q sets ΓP +t , t ∈ Fq , partition F2q into sets of size q. Moreover, for distinct such polynomials P, Q and any s, t ∈ Fq , |ΓP +s ∩ ΓQ+t | ≤ r. Proof. The r nonconstant coefficients (i.e., all coefficients except the additive constant t) can be chosen independently, giving q r polynomials. Each graph contains one point for each x ∈ Fq , and a point (x, y) belongs to the unique translate with t = y − P (x). Finally, P − Q + s − t is nonzero because P and Q differ in a nonconstant coefficient. It has degree at most r and therefore at most r roots, which bound the number of intersection points.

3

The New Coloring Algorithm

We first formulate Barenboim’s algebraic coloring procedure [1] as a general list-coloring primitive and combine it with the degree-halving strategy of [9]. We then show how hashing can be used to improve the complexity of the algorithm and prove Theorem 1.1. The only external distributed subroutines needed for the proof of the main theorem are Theorems 2.1 and 2.2.

3.1

Basic Algebraic List Coloring with Bounded Outdegree

The following primitive is Barenboim’s polynomial coloring procedure [1], stated for arbitrary color lists and with an explicit dependence on the color-space size. We are given an oriented graph H, a proper auxiliary γ-coloring ψ, and a list Lv ⊆ [C] at each node v. Choose a prime power q and an integer r ≥ 1 such that C ≤ q2

and 6

γ ≤ qr .

(a) Choose a set with many available colors (b) Remove conflicts with outneighbors y

F27

6 5 4 3 2 1 0

(0, 0)

shift t available 0 Qv 5 1 4 2 4 3 4 4 4 5 4 6 4

(2, 4)

(3, 2)

(4, 2)

–

–

–

Sv Qu1 –

Qu2

–

–

choose

0 1 2 3 4 5 6 x

available color in Lv

(1, 1)

|Sv | ≥ |Lv |/q

5 − 2 − 2 = 1 available color

Figure 1: Algebraic list coloring with q = 7, r = 2, and two outneighbors. (a) The shaded cells show the seven sets ΓX 2 +t defined in (1); black dots mark the 29 colors in Lv . The selected set Qv = ΓX 2 contains five available colors. (b) The outneighbors’ sets Qu1 = Γ2X 2 −X and Qu2 = Γ2X 2 +2X+6 each exclude two candidates, leaving (4, 2) available. All arithmetic is over F7 .

Represent the colors in [C] by distinct pairs in F2q and identify colors with these pairs. To each auxiliary color i ∈ [γ], assign a distinct polynomial Pi with zero constant coefficient and degree at most r. Such an assignment exists by Lemma 2.3. All nodes use the same representation of colors and assignment of polynomials. Each node chooses the constant term of its polynomial so that the corresponding set contains as many available colors as possible. It then chooses an available color outside the sets selected by its outneighbors. Figure 1 illustrates these two steps. The following pseudocode gives the details. Algebraic list coloring at node v 1. Choose a set. Using the graph notation from (1), choose tv ∈ Fq maximizing |Lv ∩ ΓPψ(v) +tv |, and set Qv = ΓPψ(v) +tv , Sv = Lv ∩ Qv . 2. Exchange descriptions. Send (ψ(v), tv ) to all neighbors and reconstruct Qu for every outneighbor u from its message. 3. Choose a color. Select a color in [

Sv \

Qu

+ u∈NH (v)

and output its original label in [C].

+ Lemma 3.1 (Algebraic list coloring). If |Lv | > rq |NH (v)| for every node v of H, the above algorithm computes a proper list coloring of H in one communication round using O(log γ + log q)bit messages. Announcing the selected colors takes one additional round with O(log C)-bit messages.

Proof. For every node v, the partition property of Lemma 2.3 gives + |Sv | ≥ |Lv |/q > r|NH (v)|.

Since ψ is proper, the same lemma gives |Qv ∩ Qu | ≤ r for every edge uv of H. The outneighbors + therefore exclude at most r|NH (v)| elements of Sv , leaving an available color in step 3. 7

For an edge oriented from v to u, the color selected by v lies outside Qu , whereas the color selected by u lies in Qu . The output is therefore a proper coloring of H from the original lists. Only the second step uses communication. Its message consists of an auxiliary color and a field element and has O(log γ + log q) bits. Announcing an actual color costs O(log C) bits. No list or candidate set is transmitted. √ For a proper auxiliary coloring with γ = O(C 2 ) colors, a field of size q = Θ( C) and √ polynomials of degree r = 4 suffice. Thus lists of size Ω(β C), with a sufficiently large constant, suffice for outdegree at most β. If the auxiliary coloring already has at most q 2 colors, quadratic polynomials suffice, and we can take Pi (X) = ai X 2 + bi X. Remark. In each degree-halving stage below, we could compute a fresh proper O(β 2 ) auxiliary coloring of each outdegree-β part using the outdegree version of Linial’s reduction (see Section 2.3 of the full version of [24]). Starting from the retained coloring, this takes O(log∗ ∆) rounds in parallel over all parts. Since β = O(q) in our applications, increasing q by a constant factor if necessary would then permit degree-2 polynomials. With hashing, the new auxiliary coloring could be reused for every hash function in the stage. This would, however, not improve the asymptotic round complexity: the smaller degree changes only constant factors in the list-size requirement, and the additional color reductions fit within the stated round bounds.

3.2

Degree Reduction without Hashing

We combine the algebraic procedure with the degree-reduction strategy of Fraigniaud, Heinrich, and Kosowski [9] and the arbdefective decomposition of Barenboim, Elkin, and Goldenberg [5]. In each stage, we color nodes with sufficiently large remaining lists so that the maximum uncolored degree is halved. We are given a (deg +1)-list-coloring instance with lists Lv ⊆ [C], where C = O(∆). We maintain a proper partial coloring and write L′v for the residual list of an uncolored node v, obtained by removing the colors used by colored neighbors from Lv . Whenever a node is colored, it announces its color to all neighbors, which update their lists before the next call. These lists only shrink and always contain more colors than the node has uncolored neighbors, since each colored neighbor removes at most one color. We use this convention throughout the remainder of the section. Initially, every node is uncolored. Compute and retain a proper auxiliary coloring with γ = O(∆2 ) colors by Theorem 2.1. Fix r = 4, let q be the least power of two satisfying C ≤ q2,

γ ≤ q4,

and initialize the degree bound ∆′ to the least power of two at least ∆. At degree bound ∆′ , we choose the outdegree bound β so that the algebraic procedure can color nodes with at least ∆′ /2 available colors. We process the parts sequentially, always using the current residual lists. Nodes left uncolored then have fewer than ∆′ /2 available colors, so their uncolored degrees are also smaller than ∆′ /2. We repeat the following stage while ∆′ ≥ 32q.3 Once the√loop ends, set d = ∆′ . We compute an auxiliary 2d-coloring of the remaining graph in O( d + log∗ n) CONGEST rounds, using Theorem 6.4 of the full version of [5]. This algorithm colors the parts of an arbdefective partition using Barenboim’s algebraic procedure from Lemma 3.1, with parameters chosen for degree bound d and temporary lists [2d]. Every node retains at least d available auxiliary colors, so one pass through the parts suffices. We then process the 2d auxiliary color classes in order, choosing and announcing actual colors from the residual lists L′v . 3

In each algebraic call here and below, activity and the polynomial translate are chosen locally from the node’s list. In round 1, active nodes send an activity flag and their polynomial description; inactive nodes send an inactive flag. Active nodes avoid sets only for active outneighbors in their part. In round 2, newly colored nodes announce their actual colors to all neighbors.

8

One degree-halving stage 1. Partition the uncolored graph. Set ∆′ β= 16q 



and apply Theorem 2.2 to the uncolored graph to obtain parts V1 , . . . , Vp , each with an orientation of outdegree at most β. 2. Color nodes with large lists. Process the parts in order. In part Vi , activate the uncolored nodes with |L′v | ≥ ∆′ /2 and apply Lemma 3.1 to the graph induced by these nodes, with their residual lists and the retained auxiliary coloring. Announce the selected colors and update the residual lists before processing the next part. 3. Update the degree bound. Replace ∆′ by ∆′ /2.

Theorem 3.2 (The basic algorithm). For C = O(∆), the above algorithm solves (deg +1)-list √ coloring deterministically in O( ∆ log ∆ + log∗ n) rounds in CONGEST. √ Proof. We first analyze a degree-halving stage. The field choice gives q = Θ( C) because γ = O(∆2 ) and C ≥ ∆ + 1. The loop condition ensures β ≥ 1 and β = Θ(∆′ /q), so Theorem 2.2 applies and produces p = O(q) parts. For each active node, the hypothesis of Lemma 3.1 holds: rqβ = 4qβ ≤ ∆′ /4 < ∆′ /2 ≤ |L′v |. Each call therefore gives a proper coloring from the residual lists. Since these exclude colors already used by colored neighbors, the partial coloring remains proper. Every node left uncolored had fewer than ∆′ /2 available colors when its part was processed. Residual lists only shrink and remain larger than the uncolored degrees, so the maximum uncolored degree is less than ∆′ /2. This justifies the updated degree bound. The decomposition and the two rounds per part take √ O(q + log∗ ∆) = O( C) (2) rounds per stage. There are O(log ∆) stages, and when the loop ends, the remaining graph has degree at most d = O(q). The auxiliary color classes for finishing are independent, and every residual list remains nonempty. Processing these classes gives a proper list coloring in √ at most 2d further rounds. √ Computing the auxiliary coloring and processing its classes takes O( d + log∗ n + d) √ = O( C + log∗ n) rounds. Together with the stages and the initial color reduction, the total is O( ∆ log ∆ + log∗ n) because C = O(∆). All messages contain auxiliary labels, field elements, or actual colors, each representable in O(log n) bits. Stopping early. We can improve the running time by stopping the degree reduction earlier and using an existing list-coloring algorithm on the remaining graph. Fix a constant a > 0 and set d = ⌈∆/ loga ∆⌉. Run the basic algorithm, stopping its degree-halving loop as soon as ∆′ ≤ d. If the ordinary stopping condition is reached first, use the finishing procedure above instead. To finish, choose a sufficiently large fixed constant a and apply the list-coloring algorithm of Fuchs and Kuhn [10] to the residual instance. In LOCAL, the algorithm of Maus and Tonoyan [24] can also finish the coloring. Corollary 3.3 (Combining with known list-coloring algorithms). For C = O(∆) and any fixed constant a > 0, the above variant computes a proper partial list coloring leaving maximum 9

√ uncolored degree at most ⌈∆/ loga ∆⌉ in O( ∆ log log ∆+log∗ n) deterministic CONGEST rounds. For sufficiently large a, completing the coloring as described above gives a full (deg +1)-list coloring within the same bound in both LOCAL and CONGEST. √ Proof. For sufficiently large ∆, the target degree is larger than the Θ( ∆) threshold at which the basic loop stops. Reaching it takes only O(a log log ∆) stages. The first assertion follows from (2). Bounded values of ∆ are covered by the finishing procedure above. The residual instance is still a (deg +1)-list-coloring instance, since each colored neighbor removes at most one color. Its degree bound is has size C = O(∆) = dO(1) . √ d, and its color space ∗ The algorithm of Fuchs and Kuhn √ [10] takes d polylog d + O(log n) CONGEST rounds. For a sufficiently large fixed a, this is O( ∆ + log∗ n), proving the second assertion.

3.3

A Short Family of Hash Functions

In the basic degree-reduction scheme, applying the list-coloring procedure of Lemma √ √3.1 over a color space of size C costs O( C) rounds per stage. The field size remains q = Θ( C) even when C ≫ ∆, so this cost does not decrease as the maximum uncolored degree ∆′ decreases. We use hashing to reduce the color space along with the degree. For the general argument, we introduce an image-preserving hash family. Definition 3.4 (Image-preserving hash family). Let N, M, R, k be positive integers with k ≤ N . A family of hash functions h1 , . . . , hR : [N ] → [M ] is image-preserving at threshold k if every set S ⊆ [N ] of size at least k satisfies max |hj (S)| > k/2. (3) j∈[R]

We apply such families with N = C and choose the threshold k proportional to the current degree bound ∆′ . The construction in Lemma 3.5 gives M = 8k = Θ(∆′ ), so M = o(C) whenever ∆′ = o(C). Choosing k = ∆′ /2 allows each stage to halve the maximum uncolored degree, as shown in Lemma 3.6. In each call, we color nodes whose image lists are sufficiently large and choose preimages from their current residual lists. All participating nodes use the same hash function, so adjacent nodes assigned different image colors choose different original colors. Lemma 3.5 (Image-preserving hash family). For integers N ≥ k ≥ 2 with k even, there is an image-preserving family at threshold k (Definition 3.4) consisting of R = ⌈log(N/k)⌉ + 3

hash functions

h1 , . . . , hR : [N ] −→ [8k].

The family can be computed by a finite deterministic procedure using only N and k. Construction. Enumerate all R-tuples of functions from [N ] to [8k] in a fixed order. Test each tuple on all k-element subsets of [N ] and return the first tuple satisfying (3) on all of them. Proof. Choose a random function h : [N ] → [8k] by assigning independent uniform images to all elements. Fix a k-element set S. If |h(S)| ≤ k/2, all images of S belong to some (k/2)-element subset of [8k]. Hence    k  e k/2   8k 1 Pr |h(S)| ≤ k/2 ≤ ≤ (16e)k/2 16−k = < 2−k . k/2 16 16 For R independently chosen functions, the probability that every function fails for this fixed set is less than 2−kR . A union bound over all k-element sets gives     N −kR eN −R k ≤ (e/8)k < 1. Pr[some k-element set fails for every function] < 2 ≤ 2 k k Thus a suitable family exists for all k-element sets, and every larger set contains such a set. The deterministic search therefore terminates and returns a family satisfying (3). Since the enumeration and all tests depend only on N and k, every node obtains the same family. 10

3.4

Coloring with Compressed Color Spaces

We use image-preserving families to adapt the color space to the current degree for general C ≥ ∆ + 1. As before, we retain a proper auxiliary O(∆2 )-coloring and maintain residual lists L′v that form a (deg +1)-list-coloring instance on the uncolored graph. Consider a stage in which the uncolored graph has maximum degree at most ∆′ , where ′ ∆ ≥ 2 is a power of two and ∆′ /2 ≤ C. Set k = ∆′ /2 and use a common image-preserving family h1 , . . . , hR : [C] → [M ] at threshold k, computed locally from C and k. We also reduce the auxiliary color space. Apply Theorem 2.1 to the retained coloring on the uncolored graph to obtain a proper coloring ψ with at most κ(∆′ )2 colors. Fix r = 4, let q ≥ 2 be the least power of two satisfying M ≤ q2, κ · (∆′ )2 ≤ q 4 , and set β = ⌊∆′ /(16q)⌋. Assume β ≥ 1 and apply Theorem 2.2 to obtain parts V1 , . . . , Vp with outdegree-β orientations. Keep these parts and orientations fixed throughout the stage. We process the parts sequentially. Within each part, we try all hash functions in order, coloring nodes whose current lists have sufficiently many distinct images. After each call, nodes announce their actual colors to update the remaining lists before the next hash function or part is processed. One degree-halving stage with hashing Iterate over the parts V1 , . . . , Vp and for each i = 1, . . . , p, try h1 , . . . , hR in order on Vi before proceeding to the next part. For each pair (i, j) ∈ [p] × [R], execute the following: 1. Select active nodes locally. Activate the uncolored nodes v ∈ Vi with |hj (L′v )| > k/2. 2. Color the image lists (round 1). Apply Lemma 3.1 to the graph induced by the active nodes, with lists hj (L′v ) ⊆ [M ], using ψ and the orientation of the part. Each active node v obtains an image color zv and chooses an actual color cv ∈ L′v with hj (cv ) = zv . 3. Update the residual lists (round 2). Permanently color each active node v with cv and announce cv to all neighbors. Uncolored neighbors remove these actual colors from their lists before the next call. Lemma 3.6 (Degree halving with hashing). Let h1 , . . . , hR : [C] → [M ] be an image-preserving hash family at threshold k = ∆′ /2 in the sense of Definition 3.4. If β ≥ 1, the stage above extends partial coloring and leaves maximum uncolored degree less than ∆′ /2 in √ the proper O(R M + log∗ ∆) rounds. It works in CONGEST when C, M ≤ nO(1) . √ Proof. The image guarantee implies M > k/2 = ∆′ /4, so the field choice gives q = Θ( M ). Since β ≥ 1, we have β = Θ(∆′ /q), and Theorem 2.2 produces p = O(q) parts. The hypotheses of Lemma 3.1 hold in every call, since q accommodates both the image colors and the auxiliary colors, and each active node has |hj (L′v )| > k/2 = ∆′ /4 ≥ 4qβ. Adjacent nodes colored in the same call receive different images under the same function and hence choose different actual colors. These colors also avoid all previously colored neighbors, so each call extends the proper partial coloring. To see that the degree is halved, suppose a node v remains uncolored with a final residual list S of size at least k. By (3), some function hj satisfies |hj (S)| > k/2. When hj was tried in v’s part, its residual list still contained S, since lists only shrink. Thus, v would have been active and colored, a contradiction. Every remaining list has size less than k, so the maximum uncolored degree is less than k = ∆′ /2.

11

The auxiliary color reduction and decomposition take O(q + log∗ ∆) rounds. Each part uses R two-round calls, so processing all p parts takes O(pR) = O(Rq) rounds. Messages contain only activity flags, auxiliary colors, field elements, or actual colors, and have O(log C + log M ) bits. Hash tables and lists are computed locally and are never transmitted. The complete algorithm. We use with M = 8k = 4∆′ and √ the family of Lemma 3.5, ′ ′ ′ R = O(log(1 + C/∆ )). Thus q = Θ( ∆ ), and β ≥ 1 whenever ∆ is at least a sufficiently large absolute constant. By Lemma 3.6, each stage then takes     √ C ∗ ′ O ∆ log 1 + ′ + log ∆ ∆ rounds. Initially, every node is uncolored. Compute and retain a proper auxiliary O(∆2 )-coloring by Theorem 2.1. Let ∆′0 be the least power of two at least ∆, and set ∆′ = ∆′0 . Repeat the stage above, replacing ∆′ by ∆′ /2 after each stage, until it falls below this constant threshold. On the remaining graph, use Theorem 2.1 with degree bound ∆′ and the retained auxiliary coloring. Process the resulting constant number of color classes in order, choosing and announcing an available actual color at each node. Proof of Theorem 1.1. Initially, the maximum degree is at most ∆′0 < 2∆. Every executed stage has even k = ∆′ /2 ≥ 2 and k ≤ ∆′0 /2 ≤ ∆ < C. Thus, Lemma 3.6 applies and justifies each update of the degree bound. The final color classes are independent and their residual lists are nonempty, so the finishing procedure colors all remaining nodes. This also covers bounded values of ∆ for which no stage is executed. At stage i, the degree bound is ∆′i = ∆′0 /2i . Extending the sum to all i ≥ 0, the degreedependent part of the running time is at most       X q √ X −i/2 C C O ∆′i log 1 + ′ ≤ O( ∆) 2 log 1 + +i ∆i ∆ i≥0 i≥0    √ C ∆ log 1 + . =O ∆ Both

P

i2

−i/2 and

P

i i2

−i/2 converge. The repeated auxiliary color reductions add at most

√
O log ∆ log∗ ∆ = O( ∆) rounds, which are absorbed by the same bound. The final graph has constant degree, so its auxiliary color reduction and greedy completion take O(log∗ ∆) rounds. Adding the initial O(log∗ n) rounds proves the claimed complexity. All messages have size O(log n) when C ≤ nO(1) , so the algorithm works in CONGEST. For arbitrary finite C, it works in LOCAL. All choices are deterministic, and the search of Lemma 3.5 gives every node the same hash family from C and k.

AI Disclosure The main ideas of this paper were developed by the authors. We used ChatGPT (5.6sol, 6 Astra, and 6.1sol) to further explore these ideas. The large language models were particularly useful in defining the hash families. We also used them to assist with the writing process. All formulations and proofs were carefully checked by the authors.

12

References [1] Leonid Barenboim. Deterministic (∆+1)-coloring in sublinear (in ∆) time in static, dynamic, and faulty networks. Journal of the ACM, 63(5):47:1–47:22, 2016. doi:10.1145/2979675. [2] Leonid Barenboim and Michael Elkin. Distributed (∆ + 1)-coloring in linear (in ∆) time. In Proc. of the 41st ACM Symp. on Theory of Computing (STOC), pages 111–120, 2009. doi:10.1145/1536414.1536432. [3] Leonid Barenboim and Michael Elkin. Deterministic distributed vertex coloring in polylogarithmic time. Journal of the ACM, 58(5):23:1–23:25, 2011. doi:10.1145/2027216.2027221. [4] Leonid Barenboim, Michael Elkin, and Fabian Kuhn. Distributed (∆ + 1)-coloring in linear (in ∆) time. SIAM Journal on Computing, 43(1):72–95, 2014. doi:10.1137/12088848X. [5] Leonid Barenboim, Michael Elkin, and Uri Goldenberg. Locally-iterative distributed (∆ + 1)coloring below Szegedy–Vishwanathan barrier, and applications to self-stabilization and to restricted-bandwidth models. In Proc. of the 37th ACM Symp. on Principles of Distributed Computing (PODC), pages 437–446, 2018. doi:10.1145/3212734.3212769. Full version: arXiv:1712.00285v2. [6] Michael Capalbo, Omer Reingold, Salil Vadhan, and Avi Wigderson. Randomness conductors and constant-degree lossless expanders. In Proc. of the 34th ACM Symp. on Theory of Computing (STOC), pages 659–668, 2002. doi:10.1145/509907.510003. URL https: //people.seas.harvard.edu/~salil/research/conductors-abs.html. [7] Yi-Jun Chang, Wenzheng Li, and Seth Pettie. An optimal distributed (∆ + 1)-coloring algorithm? In Proc. of the 50th ACM Symp. on Theory of Computing (STOC), pages 445–456, 2018. doi:10.1145/3188745.3188964. [8] Yi-Jun Chang, Tsvi Kopelowitz, and Seth Pettie. An exponential separation between randomized and deterministic complexity in the LOCAL model. SIAM Journal on Computing, 48(1):122–143, 2019. doi:10.1137/17M1117537. [9] Pierre Fraigniaud, Marc Heinrich, and Adrian Kosowski. Local conflict coloring. In Proc. of the 57th IEEE Symp. on Foundations of Computer Science (FOCS), pages 625–634, 2016. doi:10.1109/FOCS.2016.73. [10] Marc Fuchs and Fabian Kuhn. List defective colorings: Distributed algorithms and applications. In 37th International Symp. on Distributed Computing (DISC), volume 281 of Leibniz International Proc. in Informatics (LIPIcs), pages 22:1–22:23, 2023. doi:10.4230/LIPIcs.DISC.2023.22. [11] Marc Fuchs and Fabian Kuhn. Greedy-like defective coloring: Distributed algorithms and applications. CoRR, abs/2608.02386, 2026. doi:10.48550/arXiv.2608.02386. [12] Mohsen Ghaffari and Christoph Grunau. Near-optimal deterministic network decomposition and ruling set, and improved MIS. In Proc. of the 65th IEEE Symp. on Foundations of Computer Science (FOCS), pages 2148–2179, 2024. doi:10.1109/FOCS61266.2024.00007. [13] Mohsen Ghaffari and Fabian Kuhn. Deterministic distributed vertex coloring: Simpler, faster, and without network decomposition. In Proc. of the 62nd IEEE Symp. on Foundations of Computer Science (FOCS), pages 1009–1020, 2021. doi:10.1109/FOCS52979.2021.00101. [14] Mohsen Ghaffari, Christoph Grunau, Bernhard Haeupler, Saeed Ilchi, and Václav Rozhoň. Improved distributed network decomposition, hitting sets, and spanners, via derandomization. In Proc. of the 2023 Annual ACM-SIAM Symp. on Discrete Algorithms (SODA), pages 2532–2566, 2023. doi:10.1137/1.9781611977554.ch97. 13

[15] Andrew V. Goldberg, Serge A. Plotkin, and Gregory E. Shannon. Parallel symmetrybreaking in sparse graphs. SIAM Journal on Discrete Mathematics, 1(4):434–446, 1988. doi:10.1137/0401044. [16] Magnús M. Halldórsson, Fabian Kuhn, Alexandre Nolin, and Tigran Tonoyan. Near-optimal distributed degree+1 coloring. In Proc. of the 54th ACM Symp. on Theory of Computing (STOC), pages 450–463, 2022. doi:10.1145/3519935.3520023. [17] Magnús M. Halldórsson, Alexandre Nolin, and Tigran Tonoyan. Overcoming congestion in distributed coloring. In Proc. of the 41st ACM Symp. on Principles of Distributed Computing (PODC), pages 26–36, 2022. doi:10.1145/3519270.3538438. [18] David G. Harris, Johannes Schneider, and Hsin-Hao Su. Distributed (∆ + 1)-coloring in sublogarithmic rounds. In Proc. of the 48th ACM Symp. on Theory of Computing (STOC), pages 465–478, 2016. doi:10.1145/2897518.2897533. [19] Öjvind Johansson. Simple distributed ∆ + 1-coloring of graphs. Information Processing Letters, 70(5):229–232, 1999. doi:10.1016/S0020-0190(99)00064-2. [20] Fabian Kuhn. Weak graph colorings: Distributed algorithms and applications. In Proc. of the 21st ACM Symp. on Parallelism in Algorithms and Architectures (SPAA), pages 138–144, 2009. doi:10.1145/1583991.1584032. [21] Fabian Kuhn and Roger Wattenhofer. On the complexity of distributed graph coloring. In Proc. of the 25th ACM Symp. on Principles of Distributed Computing (PODC), pages 7–15, 2006. doi:10.1145/1146381.1146387. [22] Nathan Linial. Locality in distributed graph algorithms. SIAM Journal on Computing, 21 (1):193–201, 1992. doi:10.1137/0221015. [23] Michael Luby. A simple parallel algorithm for the maximal independent set problem. SIAM Journal on Computing, 15(4):1036–1053, 1986. doi:10.1137/0215074. [24] Yannic Maus and Tigran Tonoyan. Local conflict coloring revisited: Linial for lists. In 34th International Symp. on Distributed Computing (DISC), volume 179 of Leibniz International Proc. in Informatics (LIPIcs), pages 16:1–16:18, 2020. doi:10.4230/LIPIcs.DISC.2020.16. Full version: arXiv:2007.15251v1. [25] Moni Naor. A lower bound on probabilistic algorithms for distributive ring coloring. SIAM Journal on Discrete Mathematics, 4(3):409–412, 1991. doi:10.1137/0404036. [26] Alessandro Panconesi and Aravind Srinivasan. On the complexity of distributed network decomposition. Journal of Algorithms, 20(2):356–374, 1996. doi:10.1006/jagm.1996.0017. [27] David Peleg. Distributed Computing: A Locality-Sensitive Approach. SIAM, 2000. [28] Václav Rozhoň and Mohsen Ghaffari. Polylogarithmic-time deterministic network decomposition and distributed derandomization. In Proc. of the 52nd ACM Symp. on Theory of Computing (STOC), pages 350–363, 2020. doi:10.1145/3357713.3384298. [29] Mario Szegedy and Sundar Vishwanathan. Locality based graph coloring. In Proc. of the 25th ACM Symp. on Theory of Computing (STOC), pages 201–207, 1993. doi:10.1145/167088.167156. [30] Amnon Ta-Shma, Christopher Umans, and David Zuckerman. Loss-less condensers, unbalanced expanders, and extractors. In Proc. of the 33rd ACM Symp. on Theory of Computing (STOC), pages 143–152, 2001. doi:10.1145/380752.380790. 14

A

Explicit Hash Functions

The hash family of Lemma 3.5 has a range of size O(k), but finding it by exhaustive search can require substantial local computation. In this appendix, we replace this search by the explicit lossless expanders of Capalbo, Reingold, Vadhan, and Wigderson [6]. Both the number of functions and the ratio between the range size and k now grow slowly with C/k. The resulting bound is weaker for large color spaces, but gives the same round complexity as Theorem 1.1 when C = O(∆). Theorem A.1 (Coloring with explicit hash functions). The (deg +1)-list-coloring problem with colors from [C], where C ≥ ∆ + 1, can be solved deterministically in √ 3 ∆ 2O((log log(4+C/∆)) ) + O(log∗ n) rounds in LOCAL, and in CONGEST when C ≤ nO(1) . The algorithm uses explicit hash functions, each of which can be evaluated in time polynomial in log C from√the common parameters and its index. In particular, for C = O(∆), the round complexity is O( ∆ + log∗ n).

A.1

From Lossless Expanders to Hash Functions

We use a bipartite graph with N left vertices, M right vertices, and left degree R. Let E(x, j) denote the jth neighbor of a left vertex x. For sets A ⊆ [N ] and B ⊆ [R], define E(A, B) := {E(x, j) : x ∈ A, j ∈ B}. A lossless expander guarantees that small sets of left vertices have many distinct neighbors. We will use the neighbor functions x 7→ E(x, j) as hash functions. The expander is only used to define these functions; it is unrelated to the communication graph. Theorem A.2 (Explicit lossless expanders [6]). There are absolute constants a0 > 0 and 0 < c ≤ 1 such that, for powers of two 2 ≤ M ≤ N , there is an explicit function E : [N ] × [R] → [M ] with 3

R ≤ 2a0 (log(2+log(N/M ))) and |E(S, [R])| ≥ 43 R|S|

whenever |S| ≤ cM/R.

(4)

Given N, M, x, j, the value E(x, j) can be computed in time polynomial in log N . Proof. We use the lossless-condenser/expander correspondence of Ta-Shma, Umans, and Zuckerman [30, Lemma 2.2.1], also stated after Definition 3.4 in [6]. We spell out the needed direction. For N = M , take R = 1 and E(x, 1) = x. Otherwise, put n = log N , m = log M , and t = n − m = log(N/M ) ≥ 1. Theorem 7.3 of [6], with ε = 1/4, gives a lossless conductor E : {0, 1}n × {0, 1}d → {0, 1}m with d = O((log(4t))3 ) = O((log(t + 2))3 ),

kmax = m − d − 2 − O(1).

Identify the bit strings with [N ], [R], and [M ], where R = 2d . The bound on d gives the claimed degree bound for an absolute a0 , and evaluation takes poly(n) = poly(log N ) time. Choose an absolute constant b ≥ 0 such that kmax ≥ m − d − b, and set c = 2−b . Then log(cM/R) = m − d − b ≤ kmax . Let S ⊆ [N ] be nonempty with |S| ≤ cM/R. Take X uniform on S and J independent and uniform on [R]. The min-entropy of X is k = log |S| ≤ kmax . By the lossless-conductor property (Definition 3.4 in [6]), the distribution of E(X, J) is within statistical distance 1/4 of a distribution Q on [M ] with Q(y) ≤ 2−(k+d) = 1/(R|S|) for every y ∈ [M ].4 Since E(X, J) lies in T := E(S, [R]) with probability one, X |T | 3 Q(y) ≤ . 4 ≤ Q(T ) = R|S| y∈T

4 Statistical distance at most 1/4 means that the probabilities assigned to any event differ by at most 1/4: P | Pr[E(X, J) ∈ A] − Q(A)| ≤ 1/4 for every A ⊆ [M ], where Q(A) = y∈A Q(y).

15

This proves (4); the empty set satisfies it trivially. For every positive integer a, define, for t ≥ 1, 3

Fa (t) := 2a⌈log log(4+t)⌉ .

(5)

For the constants a0 and c from Theorem A.2, we can choose an absolute positive integer a such that 3 2a0 (log(3+log t)) ≤ cFa (t) for all t ≥ 1. (6) Such a choice exists because the two cubed expressions differ by at most a constant factor and are bounded away from zero. The ceiling makes Fa (t) an integer, and for each fixed a, 3 Fa (t) = 2O((log log(4+t)) ) . Lemma A.3 (Explicit image-preserving hash family). There is an absolute positive integer a such that, for all integers N ≥ 2 and 1 ≤ k ≤ N , there is an explicitly computable image-preserving family at threshold k (Definition 3.4) of functions h1 , . . . , hR : [N ] → [M ] with R ≤ Fa (N/k),

k ≤ M ≤ 2kFa (N/k),

M < 2N.

Each value hj (x) can be computed in time polynomial in log N . Construction. Choose a satisfying (6). Let N ′ be the least power of two at least N , and let M be the smaller of N ′ and the least power of two at least kFa (N/k). If M = N ′ , use the single function h1 (x) = x. Otherwise, construct the function E of Theorem A.2 for these N ′ , M , embed [N ] into [N ′ ], and set hj (x) = E(x, j), j ∈ [R]. The construction depends only on N and k, so every node obtains the same family. Proof. The choice of M gives all claimed range bounds, including M ≤ N ′ < 2N . If M = N ′ , the image guarantee is immediate. Otherwise, M ≥ kFa (N/k) ≥ k and N ′ < 2N , so Theorem A.2 and (6) give 3 R ≤ 2a0 (log(3+log(N/k))) ≤ cFa (N/k) ≤ Fa (N/k). Consequently, cM/R ≥ k. For every k-element set S, R X

|hj (S)| ≥

j=1

R [

hj (S) = |E(S, [R])| ≥ 43 Rk.

j=1

Some image therefore has size at least 3k/4 > k/2. A larger set contains a k-element subset and inherits the guarantee. Each function is evaluated using the neighbor algorithm of Theorem A.2, without storing a table or searching over families.

A.2

The Coloring Algorithm

Fix a as in Lemma A.3. We use the setup of Section 3.4 with the family of Lemma A.3, taking N = C and k = ∆′ /2. Compute ψ, q, and β as there. If β ≥ 1, execute the same degree-halving stage, trying all hash functions within each part before proceeding to the next part. If β = 0, process the auxiliary color classes of ψ in order, choosing and announcing an available actual color at each node. This colors all remaining nodes and ends the algorithm. Lemma A.4 (Degree halving with explicit hashing). The stage above extends the proper partial coloring and either leaves maximum uncolored degree less than ∆′ /2 or colors all remaining nodes, in √  O ∆′ Fa (2C/∆′ )3/2 + log∗ ∆ rounds. It works in CONGEST when C ≤ nO(1) . 16

Proof. Write Φ := Fa (2C/∆′ ) for this proof. Since k = ∆′ /2 and k ≤ M ≤ 2kΦ, the field choice gives √ q = O( ∆′ Φ). (7) If β ≥ 1, Lemma 3.6 gives the claimed degree reduction and a proper extension of the coloring in √ √
O(R M + log∗ ∆) = O ∆′ Φ3/2 + log∗ ∆ rounds, since R ≤ Φ and M ≤ ∆′ Φ. It remains to analyze the finishing procedure. Here β = 0, so ∆′ < 16q. Together with (7), this implies Φ = Ω(∆′ ). Equivalently, there is an absolute constant K > 0 such that ∆′ ≤ KΦ. Processing the independent auxiliary color classes takes O((∆′ )2 ) rounds, and √ √ √
(∆′ )2 = ∆′ (∆′ )3/2 ≤ K 3/2 ∆′ Φ3/2 = O ∆′ Φ3/2 . Every node has an available actual color because its residual list remains nonempty. Thus this procedure also extends the proper partial coloring within the claimed bound. Since M < 2C, the CONGEST guarantee of Lemma 3.6 applies when C ≤ nO(1) . The finishing procedure sends only auxiliary labels and actual colors, so it satisfies the same message bound. The complete algorithm. Compute and retain the initial proper auxiliary O(∆2 )-coloring by Theorem 2.1. Let ∆′0 be the least power of two at least ∆, and set ∆′ = ∆′0 . Repeat the stage above, replacing ∆′ by ∆′ /2 after each stage, until the finishing procedure is used. For ∆′ = 2, we have β = 0, so the algorithm always terminates. Proof of Theorem A.1. Initially, the maximum degree is at most ∆′0 < 2∆. In every stage, 1 ≤ k = ∆′ /2 ≤ ∆′0 /2 ≤ ∆ < C, so Lemma A.4 applies. Each stage extends the proper partial coloring and either halves the degree bound or colors all remaining nodes. Since the algorithm terminates, this proves correctness. At stage i, the degree bound is ∆′i = ∆′0 /2i . Thus, 2C/∆′i ≤ 2i+1 C/∆ and ∆′i < 2∆ 2−i . By Lemma A.4, the degree-dependent cost is at most √ X −i/2 O( ∆) 2 Fa (2i+1 C/∆)3/2 . (8) i≥0

This includes the finishing procedure. Set t = C/∆ ≥ 1 and ℓ = log(4 + t). For every i ≥ 0, log log(4 + 2i+1 t) ≤ log(ℓ + i + 1) ≤ log ℓ + log(i + 2). Using (x + y)3 ≤ 4(x3 + y 3 ) for nonnegative x, y, and absorbing the ceiling in (5), we obtain 3

3

Fa (2i+1 t)3/2 ≤ 2O((log log(4+t)) ) · 2O((log(i+2)) ) . The constants in both exponents are absolute. Because (log(i + 2))3 = o(i), the series X 3 2−i/2 2O((log(i+2)) ) i≥0

converges to an absolute constant. Substituting into (8) proves the claimed degree-dependent √ bound. The auxiliary color reductions contribute O(log ∆ log∗ ∆) = O( ∆) rounds. Adding the initial O(log∗ n) rounds proves the claimed complexity. The hash evaluation and message-size bounds follow from Lemmas A.3 and A.4. All choices are deterministic, and every node obtains the same hash family from the common parameters C and k.

17

Related documents

• Distributed $(Δ+1)$-Coloring in $O(\sqrtΔ+\log^* n)$ Rounds#1328165
• Uniform Sampling of Proper Graph Colorings via Soft Coloring and Partial Rejection Sampling#1117362
• Improved SDP Coloring of 3-Colorable Graphs from Recursive Gaussian Certificates#1118757
• Ordered matchings versus triangles via pseudorandom triangle-free graphs#1014222
• Truly Work-efficient Parallel Deterministic $(Δ+1)$-coloring and Maximal Independent Set#441765