Distributed Coloring of Hypergraphs

Abstract

For any integer $r \ge 2$, a linear r-uniform hypergraph is a generalization of ordinary graphs, where edges contain r vertices and two edges intersect in at most one node. We consider the problem of coloring such hypergraphs in several constrained models of computing, i.e., computing a partition such that no edge is fully contained in the same class. In particular, we give a $\textrm{poly}(\log \log n)$-round randomized Local algorithm that computes a $O(\varDelta ^{1/(r-1)})$-coloring w.h.p. This is tight up to polynomial factors of the time complexity as $\varOmega (\log _\varDelta \log n)$ distributed rounds are necessary for even obtaining a $\varDelta$-coloring, where $\varDelta$ is the maximum degree, and tight up to logarithmic factors of the number of colors, as $\varTheta ((\varDelta /\log \varDelta )^{1/(r-1)})$ colors are necessary for existence. We also give simple algorithms that run in O(1)-rounds of the Congested Clique model and in a single-pass of the semi-streaming model.

1 Introduction

In a seminal work [33], Linial opened the field of distributed computing with upper and lower bounds on the problem of finding a coloring of a distributed network. Since then, a large body of work has been committed to finding colorings faster and with fewer colors [5, 12, 25, 26]. The goal is usually to find a $\varDelta + 1$-coloring where $\varDelta$ is the maximum degree of the network, a number which ensures that the graph can be colored without any monochromatic edge.

One direction that has been left largely unexplored is that of finding colorings of hypergraphs. Hypergraphs generalize traditional graphs, replacing edges with hyperedges. Each hyperedge corresponds to a set of nodes without a fixed upper bound on the size of the set. A hypergraph is said to be r-uniform or of (uniform) rank r if its hyperedges all have cardinality r. A hypergraph is called linear (or simple) if no pair of hyperedges shares more than a single node¹. As in graphs, a valid coloring is one without monochromatic edges. Erdős and Lovász showed that every r-uniform hypergraph of maximum degree $\varDelta$ has a chromatic number of no more than $O(\varDelta ^{1/(r - 1)})$, and further that this bound is tight [17]. Frieze and Mubayi [21] obtained an improved (and also tight) bound of $O((\varDelta /\log \varDelta )^{1/(r - 1)})$ colors for linear hypergraphs of rank $r\ge 3$. This research leaves a large gap between the $\varDelta + 1$-coloring that can be computed in the traditional graph model, and what is theoretically possible.

In this paper, we focus on the following question; given an r-uniform linear hypergraph in the Local model, what is the fewest number of rounds needed to compute a $\tilde{\varTheta }(\varDelta ^{1/(r - 1)})$-coloring²? More generally, what is the round complexity of k-coloring, for each value of k at least $\varTheta (\varDelta ^{1/(r-1)})$ and at most $\varDelta$?

One well-known approach to solving this problem would be an application of the Lovász Local Lemma (LLL). Indeed, LLL was first introduced in a paper of Erdős and Lovász as a tool for coloring hypergraphs [17]. Starting with the work of Moser and Tardos [35], a series of successive works provide constructive, distributed techniques giving an $\log ^{O(1)} n$-round algorithm in both the randomized [14, 35] and deterministic [11, 14, 38] setting. Our result provides a rare case where a $\textrm{poly}(\log \log n)$-round algorithm is known for a problem with a strict LLL formulation, even on high-degree graphs.

1.1 Our Results

Our main result is a randomized $\log ^{O(1)} \log n$-round distributed algorithm in the Local model for finding a $O(\varDelta ^{1/(r - 1)})$-coloring, w.h.p. This provides a significant improvement over the $O(\log n)$ round algorithm given using the LLL based approach. It comes close to the recent lower bound of $\varOmega (\log _{r\varDelta } \log n)$ for coloring with $\varDelta$ colors, due to Balliu et al. [4].

It is worth noting the large gap between the $\tilde{\varTheta }(\varDelta ^{1/(r - 1)})$-coloring that is achieved by our algorithm, and the lower bound of $\varOmega \left( \log _{\varDelta } \log n \right)$ on finding a $\varDelta$-coloring. This suggests that the complexity of hypergraph coloring “plateaus” between $\varDelta$ and $\tilde{\varTheta }(\varDelta ^{1/(r - 1)})$, which contrasts with the significant gap in complexity between $\varDelta$-coloring and $\varDelta ^2$-coloring in traditional graphs. The lower bound for $\varDelta$-coloring is particularly surprising as, unlike in the graph case, r-uniform hypergraphs are $O(\sqrt{\varDelta })$-colorable when $r \ge 3$, leading to a significant gap.

We also give simple algorithms for $o(\varDelta ^{1/(r-1)})$-coloring in two models: an O(1)-round algorithm in the Congested Clique model, and a single-pass streaming algorithm using $\tilde{O}(n)$ space. For completeness, we supplement the distributed results with two additional results: An $O(\log ^* n)$ round deterministic algorithm for computing an $\tilde{O}\left( r \cdot \varDelta ^{r/(r - 1)} \right)$-coloring, and the tightness of that time bound. These results build on the $O(\log ^* n)$-round algorithm for $O(\varDelta ^2)$-coloring graphs and matching lower bound due to Linial [33].

1.2 Related Work

The related problem of $\varDelta +1$-coloring graphs has been studied extensively. The current best randomized Local algorithm is due to Chang et al. [12], and uses $O(\log ^3 \log n)$ rounds when using the recent $\textrm{poly}(\log n)$-round deterministic algorithm of [25] as a subroutine. The best known complexity in terms of $\varDelta$ is $O(\sqrt{\varDelta \log \varDelta } + \log ^* n)$ [5, 34].

As for distributed symmetry-breaking in hypergraphs, $\textrm{poly}(\log n)$ algorithms are known for Maximal Independent Set (MIS) [28, 30, 31]. Hypergraph maximal matching (HMM) has received more attention, in part due to existing reductions from some graph problems to HMM, notably edge-coloring [20]. $\tilde{O}(\textrm{poly}(\log n,r))$-round deterministic and $\tilde{O}(\textrm{poly}(\log \log n, \log \varDelta ,r))$-round randomized algorithms are known for HMM [20, 24, 29].

Brandt et al. recently showed that finding w.h.p. a $\varDelta$-coloring in graphs requires $\varOmega (\log _{\varDelta } \log n)$ rounds [8]. This uses the round elimination framework, which was automatized by Brandt [7] and applied in numerous works. Much of the work has been on graph problems, but the basic formulation also applies to hypergraph problems. In fact, Balliu et al. recently proved lower bounds for hypergraph coloring, strong coloring, MIS and maximal matching [4]. Most relevant to this paper, they showed that randomized hypergraph $\varDelta$-coloring requires $\varOmega (\log _{r\varDelta } \log n)$ rounds in Local. Their proof involves finding a fixed point for the round elimination technique, a method previously applied by the same authors to the graph $\varDelta$-coloring problem [3].

In the streaming setting, there are recent single-pass randomized algorithms for $\varDelta +1$-coloring [1] and $\varDelta$-coloring graphs [2] using $O(n\,\textrm{poly}(\log n))$ bits of memory. The only related work on hypergraphs is on the 2-coloring problem [37] (a.k.a., Property B), where the randomized algorithm matches the sequential results but deterministic algorithms are shown to be too weak. In the Congested Clique model, O(1)-round algorithms are known for $\varDelta +1$-coloring graphs, both randomized [9] and deterministic [15], but we are not aware of any similar hypergraph results.

The Lovász local lemma technique was first introduced in [17] and applied there specifically to the hypergraph coloring problem studied here. It has had an outsize importance to numerous combinatorial problems. A general and efficient algorithm was given by Moser and Tardos [35]. It is highly parallel in nature, which allows for efficient implementations in distributed computing.

The LLL is particularly important in distributed computing due to the discovery of a time hierarchy for a large class of problems known as LCLs (Locally Checkable Labeling problems). An LCL task consists of assigning labels to node and edges satisfying some locally checkable property (e.g., in coloring, adjacent nodes must receive distinct labels). On bounded degree graphs, every LCL that runs in $o(\log n)$ distributed (randomized) rounds can be sped up to $O(T_{{\textsf{LLL}}})$ rounds, where $T_{{\textsf{LLL}}}$ is the round complexity of LLL [13]. The Moser-Tardos algorithm runs in $O(\log ^2 n)$-rounds of Local, later improved to $O(\log n\cdot \log \varDelta )$ [14, 22] in general and to $O(\log n)$ [14] for weaker forms of LLL. In particular, it gives an $O(\log ^2 n)$-round algorithm for $O(\varDelta ^{1/(r-1)})$-coloring (general) hypergraphs. It is known that $T_{{\textsf{LLL}}} = \varOmega (\log _\varDelta \log n)$ [8], but there is currently a huge gap for large $\varDelta$. There have been many attempts at obtaining improved algorithms. Fischer and Ghaffari [19] gave an $O(\varDelta ^2 + \textrm{poly}(\log \log n))$-round algorithm, which largely answers the question for low-degree graphs. Their algorithm (and the ones that follow) only work for LLLs with polynomially-weakened criterion, a weaker form insufficient for hypergraph coloring with an optimal number of colors. There are recent results on still weaker forms of LLL [16], certain splitting problems [27], or restricted classes of graphs [10], but we are not aware of other distributed results that yield $\textrm{poly}(\log \log n)$-round solutions to strict forms of LLL.

Outline. The next section provides definitions and some key results from the literature. Section 3 provides a simple partitioning approach, enabling algorithms for streaming, Congested Clique, and Local. An improved Local algorithm is given in Sect. 4. Additional results follow in Sect. 5.

2 Preliminaries

Let $G = (V,E)$ be a hypergraph. For any node $v \in V$, let $d_v$ be the degree of v, defined as the number of edges in E containing v. Let $\varDelta$ be the maximum degree of G and let n be the number of nodes in G. We assume that every node in G knows the values of both $\varDelta$ and n.

Definition 1

(Underlying Graph). The underlying graph of a hypergraph $G = (V,E)$ is the graph $G' = (V, E')$ formed by replacing each hyperedge of rank r with the r-clique, i.e., $E' = \lbrace (u,v) \in \left( {\begin{array}{c}V\\ 2\end{array}}\right) \mid \exists e \in E, \lbrace u,v \rbrace \subseteq e \rbrace$ (Fig. 1, left).

Note that the underlying graph has maximum degree $r\varDelta$.

Fig. 1.

(Left) a hypergraph and its underlying graph. (Right) a colored hypergraph and the subhypergraph induced by the blue vertices. (Color figure online)

Definition 2

(Induced Subhypergraph). Let $V' \subseteq V$, the subhypergraph $G[V']$ induced by $V'$ is the hypergraph $G'=(V',E')$ formed by only keeping edges whose endpoints are all in $V'$, i.e., $E' = \lbrace e\in E \mid e\subseteq V' \rbrace$ (Fig. 1, right).

Importantly, the induced subhypergraph is defined s.t. an edge disappears if at least one of its vertices is not part of $V'$, rather than becoming an edge of rank $r' < r$. Thus, an induced subhypergraph of a rank r hypergraph is also rank r.

Definition 3

(Hypergraph coloring). A coloring of a rank r hypergraph $G = (V,E)$ is a assignment $\psi$ of colors to the nodes such that every edge $e \in E$, contains a pair of vertices $v_i,v_j \in e, \psi (v_i) \ne \psi (v_j)$ (Fig. 2).

Fig. 2.

(Left) an invalid coloring, containing a monochromatic hyperedge. (Center) a valid coloring which is not a strong coloring. (Right) a strong coloring.

We say an edge is monochromatic if $\psi (v_i) = \psi (v_j)$ for all $v_i,v_j \in e$. A valid coloring is a coloring without any monochromatic edge. It may be equivalently defined as a coloring such that the subhypergraph induced by each color class is empty, i.e., containing no hyperedges. Note that coloring a hypergraph with edges of minimum cardinality r is no harder than coloring a r-uniform hypergraph – it trivially reduces to it. A strong³ coloring of a hypergraph $G = (V,E)$ is a coloring of the vertices such that no two adjacent vertices share a color. A strong coloring may be defined as a proper coloring of the underlying graph.

Problem 1

The distributed c-coloring problem for rank r hypergraphs

• Input. A hypergraph $G = \{V,E\}$ with minimum rank r and an integer c.

• Output. A coloring of G using at most c colors.

2.1 Communication Model

In this paper we consider two models of communication, Local and Congested Clique. In both, communication is done over synchronous rounds, and each node has some globally unique $\varTheta (\log n)$-bit ID. In Local, in each round, each node can only send messages to its neighbors in the graph, but the messages can be arbitrarily large. Congested Clique removes the locality constraint and adds congestion. In this model, nodes may only send messages of size $O(\log n)$ bits, but their recipients can be all other nodes in the graph. I.e., while in Local the graph of communication is also the input graph, in Congested Clique nodes are restricted in bandwidth but not who they can talk to.

2.2 An LLL for Hypergraph Coloring

In this section we provide an overview of the key results underpinning the application of the Lovász Local Lemma to the problem of hypergraph coloring.

Lemma 1

(Lovász Local Lemma, [17]). Consider a set $\mathcal {E}$ of events such that for each $A \in \mathcal {E}$:

• 1. $\Pr [A]\le p < 1$, and

• 2. $A \in \mathcal {E}$ is mutually independent of a set of all but at most d of the other events.

If $4pd \le 1$ then with positive probability, none of the events in $\mathcal {E}$ occur.

Informally, Lemma 1 states that given a set of events that are sufficiently independent, with a low enough probability of failure, then there is a positive probability of global success. As LLL instances are locally checkable, they are a natural tool for use in distributed algorithms. Hypergraph coloring was the first problem to be solved using Lemma 1 [17].

Lemma 2

([17]). Any hypergraph G with maximum degree $\varDelta$ and rank r can be colored with $(4r \cdot \varDelta )^{1/(r - 1)}$ colors.

Proof

Let $k = \lceil (4 r \cdot \varDelta )^{1/(r - 1)} \rceil$. Consider the uniform probability distribution over the set of k colors. Further, as an edge has at least r vertices, the probability p of an edge being monochromatic is at most $p \le \frac{k}{k^r} \le \frac{1}{4 r \cdot \varDelta }$. As each hyperedge is adjacent to at most $d \le r \cdot \varDelta$ other edges, the event of an edge being monochromatic is dependent on at most $r \cdot \varDelta$ other events. Hence, by Lemma 1 as $4 pd \le 4 \frac{1}{4r\varDelta } r\varDelta \le 1$, there exists a k-coloring of G.

Lemma 2 provides an immediate method of computing a $(4r \cdot \varDelta )^{1/(r - 1)}$-coloring by brute force. The breakthrough work by Moser and Tardos [35] provided a $O(\log ^2 n)$ randomized Local algorithm for LLL, later improved to $O(\log n\cdot \log d)$ rounds [14, 22].

Theorem 1

There is a $\textrm{poly}(\log n)$-round deterministic Local algorithm that computes a $(4r \cdot \varDelta )^{1/(r - 1)}$-coloring of a hypergraph with n vertices, rank r and maximum degree $\varDelta$. This holds even if the nodes’ IDs are of order $\exp (\textrm{poly}(n))$.

Proof

There is an LLL formulation of hypergraph k-coloring, for $k = (4r \cdot \varDelta )^{1/(r - 1)}$, by Lemma 2. Thus the distributed LLL algorithm of [35] (and [14]) gives a randomized $\textrm{poly}(\log n)$-round algorithm to find such a coloring. This is a locally checkable labeling problem, which implies by the network decomposition result of [38] that there exists a $\textrm{poly}(\log n)$-round deterministic algorithm for the problem. To handle large IDs, one can either use the improved network decomposition algorithm of [23] or run Linial’s algorithm to reduce IDs to $\textrm{poly}(n)$ [33].

2.3 Shattering and Concentration Bounds

In the shattering technique, a randomized algorithm is first used to solve a large subset of the graph so that the unsolved parts of the graph induce small connected components.

Lemma 3

(Lemma 4.1 of [12]). Consider a randomized procedure that generates a subset $\textsf{Bad}\subseteq V$ of vertices. Suppose that for each $v \in V$, we have $\Pr [v \in \textsf{Bad}] \le \varDelta ^{-3c}$, and each event $v\in \textsf{Bad}$ is determined by the random choices within distance c of v. W.p. $1-n^{-\varOmega (c')}$, each connected component in $G[\textsf{Bad}]$ has size at most $(c' /c)\varDelta ^{2c} \log _\varDelta n$.

Lemma 4

(Chernoff bounds). Let $\{X_i\}_i$ be a family of independent random variables taking values in [0, 1], and let $X=\sum _i X_i$.

$$\begin{aligned} \Pr [X\ge (1+\delta )\mathop {\mathrm {\mathbb {E}}}\limits [X]]&\le \exp (-\min (\delta ,\delta ^2) \mathop {\mathrm {\mathbb {E}}}\limits [X]/3),&\forall \delta >0,\end{aligned}$$

(1)

$$\begin{aligned} \Pr [X\le (1-\delta )\mathop {\mathrm {\mathbb {E}}}\limits [X]]&\le \exp (-\delta ^2 \mathop {\mathrm {\mathbb {E}}}\limits [X]/2),&\forall \delta \in (0,1). \end{aligned}$$

(2)

As corollary of Eq. (1) when $\mathop {\mathrm {\mathbb {E}}}\limits [X]>0$, $\forall t \ge 2\mathop {\mathrm {\mathbb {E}}}\limits [X]$, $\Pr [X \ge t] \le \exp (-t/6)$.

3 Simple Splitting Primitive and Its Applications

We first consider a simple zero-round randomized primitive (see Algorithm 1) for splitting the vertex set and apply it in three different models. The splitting forms a defective coloring, defined as follows.

Given a coloring of the vertices, the defect $\textrm{def}(v)$ of a node $v \in V$ is the number of monochromatic edges incident to v, i.e., the number of incident edges whose nodes all have the same color as v. A coloring is d-defective if $\textrm{def}(v) \le d$ for all nodes v. A 0-defective coloring is a normal valid coloring.

Lemma 5

Consider the partition computed by ${ \textsc {Split} }{} (V,\varDelta ,x)$. The probability that a given node is in $V_{\textsf{Bad}}$ is at most $\exp (-\eta /6) = \exp (-\varDelta /(3x^{r-1}))$.

Proof

Observe first that for any edge e incident to v to be monochromatic, every vertex other than v in e must pick the same color as v. As there are x colors, the probability of any set of $r-1$ nodes choosing the same specified color is $1/x^{r - 1}$. The expected defect of v is therefore $\mathop {\mathrm {\mathbb {E}}}\limits [\textrm{def}(v)] = d_v/x^{r - 1}$. Since the hypergraph is linear, edges incident on v share no other vertex. Therefore, once conditioned on v’s choice of random color, whether each edge incident on v is monochromatic is independent from whether other edges incident on v are monochromatic. Using that $\eta \ge 2 d_v/x^{r-1} = 2 \mathop {\mathrm {\mathbb {E}}}\limits [\textrm{def}(v)]$, and applying Lemma 4 (Chernoff), we get that $\Pr [\textrm{def}(v) \ge \eta ] \le \exp (- \eta / 6)$.

Lemma 6

Suppose we run ${ \textsc {Split} }{} (V,\varDelta ,x)$ with $x \le (\varDelta /(24 \log (r\varDelta )))^{1/(r-1)}$. Then, $G[V_\textsf{Bad}]$ consists of connected components of size $O(\varDelta ^2 \log n)$ (i.e., the graph is shattered), w.h.p. If $x \le (\varDelta /(6\log n))^{1/(r-1)}$, then $V_\textsf{Bad}$ is empty, w.h.p.

Proof

The claim that $V_\textsf{Bad}=\emptyset$ when $x \le (\varDelta /\log n)^{1/(r-1)}$ follows from Lemma 5. Otherwise, the set $V_{\textsf{Bad}}$ consists of the nodes of defect at least $\eta =2\varDelta /x^{r-1}\ge 48\log (r\varDelta )$. By Lemma 5, the probability that $\textrm{def}(v) \ge 48\log (r\varDelta )$ is less than $(r\varDelta )^{-8}$. Each event $v\in V_\textsf{Bad}$ is fully determined by the random choices of v and its at most $r \varDelta$ neighbors. The lemma now follows from Lemma 3.

Lemma 5 immediately implies a single-round randomized algorithm to produce an $O\left( (\varDelta /\log n)^{1/(r-1)}\right)$ coloring with a defect of $O(\log n)$, w.h.p., when $\varDelta = \varOmega (\log n)$. It suffices then to solve the coloring problem on hypergraphs of degree $\varDelta =O(\log n)$. Further, we observe the following.

Lemma 7

Suppose we run ${ \textsc {Split} }{} (V,\varDelta ,x)$ and that we further color each subgraph $H = G[X]$ where $X \in \{V_i\}_i \cup V_\textsf{Bad}$ with $O(\varDelta (H)^{1/(r-1)})$ colors. The coloring of G obtained by concatenating these colorings uses $O(\varDelta ^{1/(r-1)})$ colors.

Proof

${ \textsc {Split} }{}$ produces x subgraphs of degree $\varDelta (H) \le \eta = 2\varDelta /x^{r-1}$ and one subgraph of small size. By assumption, the total number of colors is on the order of

$$ \sum _{i=1}^x \varDelta (H)^{1/(r-1)} + \varDelta ^{1/(r-1)} \le x \cdot \eta ^{1/(r-1)} + \varDelta ^{1/(r-1)} \le 3 \varDelta ^{1/(r-1)}. $$

3.1 Streaming Algorithm

We first give a simple application of the Split algorithm to the semi-streaming model. Introduced in [18, 36], the semi-streaming model is a model of computation for solving problems on massive graphs with an $O(n\,\textrm{poly}\log n)$ amount of storage space. The goal of the semi-streaming model is to provide an algorithm that can compute a solution to graph problems without needing to store the complete graph explicitly.

In the semi-streaming model, the input graph $G = (V,E)$ is given as a stream of edge changes (insertions and deletions). For hypergraphs, the stream is instead an ordered list of hyperedge changes. After each edge change, a semi-streaming algorithm is given some amount of time to process the change, with the restriction that no more than $O(n\,\textrm{poly}\log n)$ space is used at any given time. The order that the edge changes are assigned is assumed to be determined by an oblivious adversary. Such an adversary has access to the algorithm being used and is capable of simulating it, but does not have access to any source of randomness being used.

Theorem 2

There exists a single-pass semi-streaming randomized algorithm for $O((\varDelta /\sigma )^{1/(r-1)})$-coloring linear hypergraphs against an oblivious adversary, where $\sigma = \min \lbrace \log \varDelta ,\log \log n \rbrace$.

Proof

When $\varDelta = O(\log n)$, the full graph is represented using $O(rn\log ^2 n)$ bits: we store it fully and color it with $O((\varDelta /\log \varDelta )^{1/(r-1)})$ colors using the method of [21]. Otherwise, we apply ${ \textsc {Split} }{} (V,\varDelta ,x)$ with $x=O\left( (\varDelta /\log n )^{1/(r - 1)}\right)$. By Lemma 5, $V_\textsf{Bad}= \emptyset$ and each $V_i$ is $O(\log n)$-defective. Thus, $O(rn\log ^2 n)$ bits suffice to represent all the subgraphs in the partition. Applying the algorithm of [21] on each of them, we use a total of $x \cdot O((\log n / \log \log n)^{1/(r-1)}) = O(\varDelta ^{1/(r-1)}/\log \log n)$ colors.

3.2 Congested Clique Algorithm

In the Congested Clique, $O(\log n)$-bit messages can be sent between any pair of vertices, not just the adjacent ones. It does not matter for our argument whether the hyperedges are represented by a separate node (as in the client-server model), or if we are given the underlying graph representation. We propose an algorithm that partitions the hypergraph into a collection of hypergraphs that can be represented in small space. Each of these can then be gathered at a single node and colored separately. Recall that the bound obtained is best possible for linear hypergraphs [21].

Theorem 3

There is a O(1)-round randomized algorithm in the Congested Clique model for $O((\varDelta /\log \varDelta )^{1/(r-1)})$-coloring r-uniform linear hypergraphs.

Proof

Apply ${ \textsc {Split} }{} (V,\varDelta ,x)$ with $x = \varDelta ^{1/r}$ to obtain a partition of V into $V_1, V_2, \ldots , V_x$ and $V_\textsf{Bad}$, where each $V_i$ is at most $\eta$-defective, $\eta = 2\varDelta /x^{r-1} = 2\varDelta ^{1/r}$. For each $i \in [x]$, send all monochromatic edges within $V_i$ to node i, which then computes an $O((\eta /\log \eta )^{1/(r-1)})$-coloring of $V_i$. Similarly, send the edges within $V_\textsf{Bad}$ to a single node and let it $O((\varDelta /\log \varDelta )^{1/(r-1)})$-color $V_\textsf{Bad}$ [21]. Concatenate these colorings to obtain a coloring of G using

$$\begin{aligned} x \cdot O((\eta /\log \eta )^{1/(r-1)})+ O((\varDelta /\log \varDelta )^{1/(r-1)}) = O((\varDelta / \log \varDelta )^{1/(r-1)}) \end{aligned}$$

colors. It remains to explain how to achieve this communication in O(1) rounds.

By Lemma 4 (Chernoff), each $V_i$ contains at most 2n/x vertices, w.h.p., and by definition each node has degree at most $\eta$ (within $V_i$). Thus, the number of monochromatic edges in each part is at most $2n/x \cdot \eta = 2\varDelta n/x^r = 2n/r$, w.h.p. They are represented in $r \cdot 2n/r = 2n$ space (of $O(\log n)$-bit words), and can be forwarded to a single node using Lenzen routing in O(1) rounds [32].

3.3 Simple LOCAL Algorithm

Suppose $\varDelta =O(\log n)$ for now, leaving the $\varDelta \in \varOmega (\log n)$ case for later. We apply ${ \textsc {Split} }{} (V,\varDelta ,x)$, where $x = (\varDelta /(24 \log (r\varDelta )))^{1/(r-1)}$ to partition V into $V_1, V_2, \ldots , V_x$ and $V_{\textsf{Bad}}$. We color $V_{\textsf{Bad}}$ with $(4r\varDelta )^{1/(r-1)}$ colors using the deterministic LLL algorithm of Theorem 1. We then color each $V_i$ by replacing each r-edge e of $G[V_i]$ by an arbitrary 2-edge $e' \subseteq e$ and applying the $\varDelta +1$-coloring algorithm of [12] on each obtained (standard) graph, in parallel. Each of these steps runs in $\textrm{poly}(\log \log n)$ rounds. We use $\eta +1 = O(\log (r\varDelta ))$ colors on each $V_i$, for a total of $x (\eta +1) = O((\varDelta \log ^{r-2} (r\varDelta ))^{1/(r-1)})$.

When $\varDelta \in \varOmega (\log n)$, we reduce the problem to coloring $O(\log n)$-degree instance by applying ${ \textsc {Split} }{} (V,\varDelta ,x)$ with $x = (\varDelta /(6\log n))^{1/(r-1)}$.

4 Improved LOCAL Algorithm

We give an improved algorithm that uses $O(r^2 \varDelta ^{1/(r-1)})$ colors, using different techniques. The main component of our method is an algorithm for triangle-free (girth 4) hypergraphs, i.e., when there are no vertices x, y, z where each pair belongs to a distinct edge.

Theorem 4

There is an $O(\textrm{poly}(\log \log n))$-round randomized Local algorithm to color a triangle-free hypergraph of rank r with $O(\varDelta ^{1/(r-1)})$ colors, w.h.p. When $\varDelta \ge 4^{r-1} (18\log n)^{(r-1)^2}$, the algorithm takes $O(\log \log \varDelta + \log ^* n)$ rounds.

The algorithm and the proof of the theorem are given in the next subsection. We then give in Sect. 4.2 a reduction of the general coloring problem (of linear hypergraphs) to the triangle-free case.

4.1 Triangle-Free Hypergraphs

We consider the following simple method ${ \textsc {GeometricTrials} }{}$ (Algorithm 2), in which the nodes try random colors from geometrically decreasing palettes. In this algorithm, all nodes initially participate in trying colors, and across $(i_{\textsf{last}}+1) \in O(\log \log \varDelta )$ successive iterations, they progressively either get colored or quit the process (joining a shattered subinstance), thereby reducing competition for other nodes. The nodes still active in iteration i induce an hypergraph of maximum degree $\varDelta _i$, where the sequence $\varDelta _0 \ldots \varDelta _{i_{\textsf{last}}}$ decreases doubly exponentially in i and $\varDelta _{i_{\textsf{last}}+1} < \varDelta _{i_{\textsf{last}}}$ is set to $\varDelta _{\textsf{goal}}= \varDelta ^{1/(r-1)}$. The quitters in iteration i are those that both fail to color themselves and whose degree remains above $\varDelta _{i+1}$.

By using geometrically shrinking palettes of initial size $K = 4\varDelta ^{1/(r-1)}$ and shrinking factor $\alpha = 1/2$, clearly, at most $O(K/(1-\alpha )) = O(\varDelta ^{1/(r-1)})$ distinct colors are used by ${ \textsc {GeometricTrials} }{}$. We show that nodes left uncolored by ${ \textsc {GeometricTrials} }{}$ can also be colored using $O(\varDelta ^{1/(r-1)})$ colors.

By definition, the nodes still active after the last iteration of the algorithm induce a graph of maximum degree $\varDelta _{\textsf{goal}}=\varDelta ^{1/(r-1)}$, which can be efficiently $O(\varDelta _{\textsf{goal}})$-colored by an algorithm from the distributed graph coloring literature. What remains to be proved is that quitters can also be efficiently colored with $O(\varDelta ^{1/(r-1)})$ colors, even though they might induce a hypergraph of degree $\omega (\varDelta ^{1/(r-1)})$. We resolve this by a shattering argument: quitting the process early occurs with sufficiently low probability, and with sufficient independence between the nodes, that early quitters form connected components of size $\textrm{poly}(\log n)$ which can be handled by the deterministic LLL algorithm of Theorem 1. The triangle-free property is crucial to the analysis of this probability: it allows us to argue that what happens in each edge incident on a node is somewhat independent from what happens in other incident edges, and so the degree decreases as needed with a high (enough) probability.

Notation. The algorithm executes a loop for $i_{\textsf{last}}+1$ iterations, where $i_{\textsf{last}}\in O(\log \log \varDelta )$. For any $i\in [0,i_{\textsf{last}}]$, we denote by $V^{(i)}$ the set of uncolored nodes trying a color in iteration i in Algorithm 2. We denote by $V_{\textsf{Good}}^{(i)}$ the nodes of $V^{(i)}$ that successfully color themselves in iteration i, and $V_{\textsf{Quit}}^{(i)}$ the nodes that abandon the process in iteration i. The remaining nodes form $V^{(i+1)}$, i.e., $V^{(i+1)} = V^{(i)} \setminus (V^{(i)}_{\textsf{Good}} \sqcup V^{(i)}_{\textsf{Quit}})$.

We also consider the sets $V_{\textsf{Good}} = \bigsqcup _{i=0}^{i_{\textsf{last}}} V^{(i)}_{\textsf{Good}}$, $V_{\textsf{Quit}} = \bigsqcup _{i=0}^{i_{\textsf{last}}} V^{(i)}_{\textsf{Quit}}$, and $V_{\textsf{Low}} = V \setminus (V_{\textsf{Good}} \cup V_{\textsf{Quit}})$. $V_{\textsf{Good}}$ are all the nodes that got colored by the process, $V_{\textsf{Quit}}$ are all the quitters, and $V_{\textsf{Low}}$ are the nodes that remained active through the whole process and thus have had their degree reduced. We have as initial condition $V^{(0)} = V$.

Degree Reduction. First, we analyze how the degree of a node behaves when all nodes in a hypergraph of maximum degree $\varDelta$ try a color u.a.r. from a set of size $K \gg \varDelta ^{1/(r-1)}$, as in GeometricTrials. There are two ways for an edge e incident on v to survive: either e itself was monochromatic, or each node of e was part of a monochromatic edge other than e. Note that these are not mutually exclusive. The first type of event is analyzed when considering splitting (Sect. 3). The following lemma analyzes the second type of event.

Lemma 8

Let $C \ge 2^{1/(r-2)}$ be a constant, and $G=(V,E)$ be a triangle-free graph of rank r and maximum degree $\varDelta$. Let each node v try a random color in $[K]=[C\cdot \varDelta ^{1/(r-1)}]$ and uncolor itself if it is part of a monochromatic edge. Let $s\in [2 \varDelta ^{1/(r-1)}/C^{r-2}, K]$ and $t\ge 2(s/C)^{r-1}$. Then w.p. at least $1-2\exp (-t/6)-(r-1)\varDelta \exp (-s/6)$, v’s degree (number of fully uncolored incident edges) becomes at most 2t.

Proof

(Proof sketch). We consider an edge e incident on v and bound the probability that each node in e other than v is part of a monochromatic edge. The survivals of edges incident on v are not necessarily independent due to 4-cycles: for two edges $e,e'$ incident on v, there might be a vertex u at distance 2 from v that is connected to both a vertex in $w \in e$ and a vertex $w' \in e'$. We handle this non-independence by arguing independence once the colors at distance 2 from v have been fixed. When fixing those colors, some edges incident on a neighbor of v might be monochromatic on the already selected $(r-1)$ colors. We bound the probability that this occurs on too many edges, so as to argue that nodes in an edge incident on v are unlikely to all pick a color that makes an edge they’re part of monochromatic. We defer the full proof to Appendix A.1

Lemma 9

Let $\varDelta _i$ be the maximum degree of active nodes in the i-th round of GeometricTrials, $K_i$ the number of colors to choose from in that round, and $C_i = \varDelta _i^{1/(r-1)}/K_i$. Then, for each live node v in the i-th round of GeometricTrials:

• v gets colored w.p. at least $1-\varDelta _i / K_i^{r-1}$.

• Let $d'_v$ be the degree of v after this round. For any $t\ge 4\varDelta _i/C_i^{(r-1)^2}$,

  $$\begin{aligned} \Pr [d'_v \le t] \ge 1 - 3(r-1)\varDelta _i \exp (-(t/4)^{1/(r-1)}C_i/6). \end{aligned}$$

Proof

For the first item, we use that each edge incident on v is monochromatic w.p. $1/K_i^{r-1}$. By union bound, v is part of no monochromatic edge w.p. at least $1-\varDelta _i / K_i^{r-1}$, in which case it gets colored. For the second item, we apply Lemma 8 with $K=K_i$, $C=C_i$, $\varDelta =\varDelta _i$, and $s = C\cdot (t/4)^{1/(r-1)}$. Note that though the lemma may not be applied with this s when $t \ge 4\varDelta$, the result still holds since v’s degree is always less than $\varDelta$.

We now analyze the probability that a node quits during GeometricTrials.

Lemma 10

For each node v, the probability that v is in $V_{\textsf{Quit}}$ is at most

$$\begin{aligned} 3(r-1)\varDelta (\log \log \varDelta ) \cdot \exp (-(\varDelta _{\textsf{goal}}/4)^{1/(r-1)}/6). \end{aligned}$$

Proof

(Proof sketch). Armed with previous technical lemmas, this proof only consists of a union bound over all iterations, summing the probabilities that v’s degree does not decrease sufficiently when it fails to get colored. The full proof is deferred to Appendix A.2.

The Full Algorithm. Our algorithm and its analysis follow naturally once GeometricTrials has been introduced and analyzed. We first run GeometricTrials. Uncolored nodes now fall into two categories: quitters and non-quitters. The non-quitters induce a graph of maximum degree $\varDelta _{\textsf{goal}}= \varDelta ^{1/(r-1)}$. When $\varDelta$ is a large enough $\textrm{poly}(\log n)$, w.h.p., there are no quitters. For smaller $\varDelta$, w.h.p., the graph induced by quitters is shattered; more precisely, it consists of connected components of size $\log ^{O(\log \log \log n)} n$. All that remains is to apply results from the literature to color those connected components, and to color the remaining other uncolored nodes of degree $O(\varDelta ^{1/(r-1)})$.

Theorem 4. There is an $O(\textrm{poly}(\log \log n))$-round randomized Local algorithm to color a triangle-free hypergraph of rank r with $O(\varDelta ^{1/(r-1)})$ colors, w.h.p. When $\varDelta \ge 4^{r-1} (18\log n)^{(r-1)^2}$, the algorithm takes $O(\log \log \varDelta + \log ^* n)$ rounds.

Proof

Recall that $\varDelta _{\textsf{goal}}= \varDelta ^{1/(r-1)}$. After GeometricTrials, each uncolored node is either in $V_{\textsf{Quit}}$ or $V_{\textsf{Low}}$, and only $O(\varDelta ^{1/(r-1)})$ colors were used. We color $V_{\textsf{Quit}}$ and $V_{\textsf{Low}}$ each with their own set of $O(\varDelta ^{1/(r-1)})$ colors, for a total number of colors of the same order of magnitude. Note that we can color them in parallel since they use distinct colors. We split the analysis depending on the value of $\varDelta$, starting with $\varDelta$ large (at least some $\textrm{poly}(\log n)$).

When $\varDelta \ge 4^{r-1}(18\log n)^{(r-1)^2}$, by Lemma 10, w.h.p., there are no nodes in $V_{\textsf{Quit}}$. This means that the only nodes that remain to be colored are in $V_{\textsf{Low}}$, so we can skip the costly application of Theorem 1 that we otherwise use to color $V_{\textsf{Quit}}$. The hypergraph induced by $V_{\textsf{Low}}$ has maximum degree $O(\varDelta ^{1/(r-1)})$. We project each hyperedge e of $G[V_{\textsf{Low}}]$ to an arbitrary 2-edge uv, $\lbrace u,v \rbrace \subseteq e$. The resulting graph also has maximum degree $O(\varDelta ^{1/(r-1)})$, and we color it in $O(\log ^* n)$ rounds with $\varTheta (\varDelta ^{1/(r-1)}) = \varOmega (\log ^{r-1} n)$ colors by the algorithm for $O(\varDelta +\log ^{1+1/\log ^* n}n)$-coloring from [39]. This gives the complexity of $O(\log \log \varDelta + \log ^*n)$ rounds for large $\varDelta$.

For smaller $\varDelta$, we color $V_{\textsf{Low}}$ with the $\textrm{poly}(\log \log n)$ algorithm of [6] for $(\varDelta +1)$-coloring. To color the nodes of $V_{\textsf{Quit}}$ efficiently, we argue that the hypergraph they induce is shattered, w.h.p. More precisely, we show that $G[V_{\textsf{Quit}}]$ consists of connected components of size $O(\log ^{1+2\log \log \varDelta }n) = \log ^{O(\log \log \log n)} n$, w.h.p.

Let $c=\log \log \varDelta > i_{\textsf{last}}$. Whether a node quits GeometricTrials is determined by the random choices within distance c from v during the process, and it occurs with probability at most $3(r-1)\varDelta (\log \log \varDelta ) \exp (-(\varDelta _{\textsf{goal}}/4)^{1/(r-1)}/6) = \exp (-\varTheta (\varDelta ^{1/(r-1)^{2}})) \le (r\varDelta )^{-3c}$ by Lemma 10, for $\varDelta$ larger than some sufficiently big constant (constant degree hypergraphs can be colored with $O(\varDelta ^2) = O(1) = O(\varDelta ^{1/(r-1)})$ colors in $O(\log ^* n)$ by [33]). By Lemma 3, the graph induced by $V_{\textsf{Quit}}$ has connected components of size $O((r\varDelta )^{2c} \log n) = \log ^{(r^{O(1)}\log \log \log n)}n$. Theorem 1 therefore colors $V_{\textsf{Quit}}$ in $\textrm{poly}(\log \log n)$ rounds, for a total complexity of $\textrm{poly}(\log \log n)$ Local rounds, and using at most $O(\varDelta ^{1/(r-1)})$ colors in total.

4.2 Reduction to the Triangle-Free Case

We now reduce the problem of coloring general linear hypergraphs to that of coloring triangle-free ones. We partition the hypergraph into hypergraphs that are either triangle-free or of polylogarithmic size. The former are solved by the algorithm of the preceding section, while the latter are solved by Theorem 1. This reduction is adapted from the work of Frieze and Mubayi [21], and modified only slightly for a distributed context, in particular avoiding a degeneracy-based coloring (that is known to require $\varOmega (\sqrt{\log n})$-rounds [33]).

The following two lemmas are stated existentially in [21], but the statements below follow immediately from the proofs of their lemmas in [21]. When splitting nodes into subsets $V_1,\ldots ,V_m$, inducing subhypergraphs $H_1,\ldots ,H_m$, where v ends in $H_{i_v}$, a pair of nodes $x,y \in N_H(v)$ is said to be covered if

• the edges $S,S' \in E$ s.t. $\lbrace v,x \rbrace \subseteq S$ and $\lbrace v,y \rbrace \subseteq S'$ are both in $H_{i_v}$;

• there exists an edge $S'' \in E$ that contains both x and y but not v ($\lbrace x,y \rbrace \subseteq S$ and $v \not \in S''$), and $S'' \in H_{i_v}$.

Intuitively, x, y is a covered pair of v if v, x, and y form a triangle that survived splitting.

Lemma 11

(Lemma 5 [21]). Let H be a linear rank r hypergraph of maximum degree $\varDelta$. Let $m = \lceil \varDelta ^{2/(3r-4)}-\varepsilon \rceil$. Suppose we partition the nodes u.a.r. into subsets $V_1, V_2, \ldots , V_m$, inducing subhypergraphs $H_1, H_2, \ldots , H_m$. Then, for each $i=1, \ldots , m$ and each $v \in V_i$,

• 1. v has degree more than $2\varDelta /m^{r-1}$ in $V_i$ w.p. at most $\varDelta ^{-5}$.

• 2. The $H_i$ neighborhood of v $N_{H_i}(v)$ contains more than $r^2 \varDelta ^2/m^{3r-4}$ covered pairs w.p. at most $\varDelta ^{-5}$.

Lemma 12

(Lemma 6 [21]). Let $\delta$ be a sufficiently small positive constant depending on r. Let L be a linear rank r hypergraph of maximum degree at most d. Suppose that each vertex neighborhood $N_L(v)$ contains at most $d^{\delta }$ covered pairs. Let $\ell = d^{1/(r-1)-\delta }$. Suppose we partition the nodes u.a.r. into subsets $W_1, W_2, \ldots , W_{\ell }$, inducing subhypergraphs $L_1, L_2, \ldots , L_{\ell }$. Then, for each $j=1, \ldots , \ell$ and each $v \in W_j$,

• 1. v has more than $2d/\ell ^{r-1}$ neighbors in $W_j$ is w.p. at most $d^{-5}$.

• 2. v belongs to more than $400r^2$ triangles within $L_j$ is w.p. at most $d^{-5}$.

Theorem 5

There is a randomized algorithm for $O(r^2 \varDelta ^{1/(r-1)})$-coloring r-uniform linear hypergraphs in $\textrm{poly}(\log \log n)$ Local rounds, w.h.p.

Proof

We reduce the problem to the case where the maximum degree is $O(\log n)$. When $\varDelta > \log n$, we apply ${ \textsc {Split} }{} (V,\varDelta ,x)$ with $x = (\varDelta / (6\log n))^{1/(r-1)}$. By Lemma 6, each of the obtained vertex sets induces a subhypergraph of maximum degree $\varDelta ' \in O(\log n)$, w.h.p. Applying a coloring algorithm that uses only $O(r^2 (\varDelta ')^{1/(r-1)})$ on each of them results in an overall coloring that uses $O(r^2\varDelta ^{1/(r-1)})$ colors in total, by Lemma 7. The $\varDelta \in \varOmega (\log n)$ degree case thus reduces to the $O(\log n)$ degree case.

By combining Lemma 11 and Lemma 12, we reduce the problem to the coloring of a collection of triangle-free hypergraphs. Nodes that fail the first (second) condition of Lemma 11 are moved to the set $V^1_\textsf{Bad}$ ($V^2_\textsf{Bad}$), and those that fail the first (second) condition of Lemma 12 are moved to $V^3_\textsf{Bad}$ ($V^4_\textsf{Bad}$), respectively. By Lemma 3, each $V^i_\textsf{Bad}$ is shattered, inducing components of size at most $N = \textrm{poly}(\log n)$. Thus, we can color each $V^i_\textsf{Bad}$ with $(4r\varDelta )^{1/(r-1)}$ colors in $\textrm{poly}(\log N) = \textrm{poly}(\log \log n)$ rounds, by the LLL algorithm of [14], for a total of $O(\varDelta ^{1/(r-1)})$ colors.

The rest of the nodes are partitioned into sets $V_1, \ldots , V_m$, each of which is $d = 2\varDelta '/m^{r-1}$-defective. Each such $V_i$ is partitioned into $W^i_1, \ldots , W^i_{\ell }$, which are $q = 2d/\ell ^{r-1}$-defective, where $\ell = d^{1/(r-1)-\delta }$. Crucially, each node in the subhypergraph $L^i_j$ induced by each $W^i_j$ is part of at most $400r^2$ triangles. Consider the underlying graph of $L^i_j$, and focus on the subgraph $M^i_j$ consisting of the edges (v, x), (v, y) involved in a covered pair x, y (with some node v). This $M^i_j$ has maximum degree $O(r^2)$, by the bound on triangle participation in $L^i_j$. We color this graph with $O(r^2)$ colors using a $\textrm{poly}(\log \log n)$-round randomized algorithm for $\varDelta +1$-coloring graphs [6, 38]. Let $W^{i,1}_j, \ldots , W^{i,c}_j$ be the vertices of each of the c color classes, where $c\in O(r^2)$. Each node that is not in any class joins one at random. For each $k \in [c]$ let $L^{i,k}_j$ be subhypergraph induced by $W^{i,k}_j$.

Note that each $L^{i,k}_j$ is triangle-free (girth 4), and like $L^i_j$ has maximum degree at most $q=2d/\ell ^{r-1}$. We apply the algorithm of Theorem 4 to each $L^{i,k}_j$ in parallel, which uses $O(q^{1/(r-1)}) = O(d^{1/(r-1)}/\ell )$ colors. So, the total number of colors used on each $V_i$ is $\ell \cdot c \cdot O(d^{1/(r-1)}/\ell ) = O(r^2 d^{1/(r-1)})$. By the same token, the total number of colors used on all the classes $V_1, \ldots , V_m$ is $m \cdot O(r^2 d^{1/(r-1)}) = m \cdot O(r^2 \varDelta ^{1/(r-1)}/m) = O(r^2 \varDelta ^{1/(r-1)})$, as desired.

5 Additional Results

We also provide two results lifting the classic $O(\varDelta ^2)$-coloring algorithm and $\varOmega (\log ^* n)$ lower bound due to Linial to the hypergraph setting. Contrary to our main results, these apply to general hypergraphs. We defer their proofs to Appendix B.

Theorem 6

There is a deterministic $O(\log ^* n)$-round Congest algorithm to $O ( r \cdot \varDelta ^{r/(r - 1)} \log (r\varDelta ))$-color hypergraphs of maximum degree $\varDelta$ and rank r.

Theorem 7

For any pair of constants r and c, no Local algorithm can find a $O(\varDelta ^c / r)$ coloring of a rank r hypergraph in fewer than $\varOmega \left( (\log ^* n) / r\right)$ rounds.

Appendices

A Missing Proofs of Main Algorithm

1.1 A.1 Proof of Lemma 8 (Degrees Decrease in GeometricTrials)

Lemma 8. Let $C \ge 2^{1/(r-2)}$ be a constant, and $G=(V,E)$ be a triangle-free graph of rank r and maximum degree $\varDelta$. Let each node v try a random color in $[K]=[C\cdot \varDelta ^{1/(r-1)}]$ and uncolor itself if it is part of a monochromatic edge. Let $s\in [2 \varDelta ^{1/(r-1)}/C^{r-2}, K]$ and $t\ge 2(s/C)^{r-1}$. Then w.p. at least $1-2\exp (-t/6)-(r-1)\varDelta \exp (-s/6)$, v’s degree (number of fully uncolored incident edges) becomes at most 2t.

Proof

As explained in the main text, an edge e incident on a node v has two ways of surviving this process: by being monochromatic itself, or by having each of its nodes be part of a monochromatic edge distinct from e.

The number of monochromatic edges incident on v corresponds to its defect in the tentative coloring, which we previously analyzed. As in the proof of Lemma 5, at most t edges survive that way, w.p. $1-\exp (-t/6)$.

We turn to the second type of surviving edges. Let us say an edge e incident on v is forbidding to v if the nodes in e other than v all have the same color. We say that a color c is forbidden to a node v if v has an incident forbidding edge whose nodes other than v are all colored c. Let F(v) be the set of edges forbidding to v. The second type of surviving edge occurs when each of its nodes selects a forbidden colors. We show that $| F(v) |$ is concentrated.

Claim

For a node v and integers $x > 0$, $t \ge 2 d_v/x^{r-2}$, $\Pr [| F(v) | \ge t] \le \exp (-t/6)$.

Proof

(Proof of Appendix A.1). An edge e is forbidding to $v\in e$ with probability $1/x^{r-2}$. Therefore, $\mathop {\mathrm {\mathbb {E}}}\limits [| F(v) |] = d_v / x^{r-2}$, and $t \ge 2\mathop {\mathrm {\mathbb {E}}}\limits [| F(v) |]$. Because v’s neighborhood is triangle-free, edges incident on v share no other vertex. Therefore, whether each edge is forbidding to v is independent of whether other edges are, and by Lemma 4 (Chernoff bound), the probability ensues.

We now bound the probability that many edges survive due to all of its nodes picking a forbidden color.

Recall $s \ge 2 \varDelta ^{1/(r-1)}/C^{r-2}$. By Appendix A.1, a node u has less than s forbidden colors w.p. $1-\exp (-s/6)$. Therefore, all the neighbors of v have less than s forbidden colors w.p. $1-(r-1)\varDelta \exp (-s/6)$. In the rest of the argument, we condition on the event that nodes at distance 2 from v forbade at most s colors to each direct neighbor of v, and fix the random choices of nodes at distance 2 from v to a specific assignment satisfying this conditioning.

Consider an edge e incident on v with vertices $v,u_1,\ldots ,u_{r-1}$. The probability that $u_i$ picks a color forbidden by the distance 2 neighbors of v it is adjacent to is at most s/K. The probability that the $r-1$ $u_i$’s do so is at most $(s/K)^{r-1}$ by the independence of their choices. Therefore, the expected number of edges that remain uncolored due to this second argument is at most $\varDelta (s/K)^{r-1}$.

Finally, for each e incident on v let $X_e$ be the indicator random variable of the event that all its nodes other than v picked a color forbidden by the nodes at distance 2 from v. Let X be the sum $\sum _{e\ni v} X_e$. The $X_e$’s are all independent once the random choices of nodes at distance 2 are fixed. Therefore, by Lemma 4 (Chernoff bound), for $t \ge 2\varDelta (s/K)^{r-1} = 2 (s/C)^{r-1}$, $\Pr [X \ge t] \le 1 - \exp (-t/6)$.

Putting everything together, w.p. at least $1 - 2\exp (-t/6) - (r-1)\varDelta \exp (-s/6)$, each of the two sources of surviving edges contributes at most t edges, for a total of at most 2t.

1.2 A.2 Proof of Lemma 10

Lemma 10. For each node v, the probability that v is in $V_{\textsf{Quit}}$ is at most

$$\begin{aligned} 3(r-1)\varDelta (\log \log \varDelta ) \cdot \exp (-(\varDelta _{\textsf{goal}}/4)^{1/(r-1)}/6). \end{aligned}$$

Proof

Recall the values of variables which dictate how nodes behave in GeometricTrials,

• $C=4, \alpha =1/2, \varDelta _{\textsf{goal}}= \varDelta ^{1/(r-1)}$,

• $C_i = C^{2^i} = 4^{2^i}, K_i = \alpha ^i \varDelta ^{1/(r-1)}$,

• $\varDelta _i = \max \lbrace (K_i/C_i)^{r-1}, \varDelta _{\textsf{goal}} \rbrace , i_{\textsf{last}}= \max \lbrace i \mid \varDelta _i > \varDelta _{\textsf{goal}} \rbrace$.

Let us analyze the probability that a live node v in the i-th iteration of GeometricTrials decreases its degree to less than $\varDelta _{i+1}$ (or gets colored). By Lemma 9, if $\varDelta _{i+1} \ge 4 \varDelta _i/C_i^{(r-1)^2}$, then v’s degree decreases to less than $\varDelta _{i+1}$ with probability

$$\begin{aligned} 1-3(r-1)\varDelta _i\exp (-(\varDelta _{i+1}/4)^{1/(r-1)}C_i/6). \end{aligned}$$

We verify that $\varDelta _{i+1} \ge 4 \varDelta _i/C_i^{(r-1)^2}$ indeed holds. Note that, by definition,

$$\begin{aligned}\varDelta _{i+1}&\ge (K_{i+1}/C_{i+1})^{r-1} = \alpha ^{(i+1)(r-1)} K C^{-(r-1)2^{i+1}} = \varDelta _i \cdot (\alpha ^{r-1} C^{-(r-1)2^{i}})\\&= \varDelta _i \cdot 4^{-(r-1)/2 -(r-1)2^i} \ge 4\varDelta _i /C_i^{(r-1)^2}. \end{aligned}$$

For each node active in iteration $i\le i_{\textsf{last}}$ (which has therefore degree at most $\varDelta _i$), by Lemma 9, the probability that its degree fails to decrease to $\varDelta _{i+1}$ or less after each live node tries a color is at most

$$\begin{aligned} 3(r-1)\varDelta _i e^{-(\varDelta _{i+1}/4)^{1/(r-1)}/6}. \end{aligned}$$

Summing over all the rounds, the probability that a node joins $V_\textsf{Quit}$ during the $i_{\textsf{last}}+1 \le \log \log \varDelta$ loop iterations of GeometricTrials is at most

$$3(r-1)\sum _{i=0}^{i_{\textsf{last}}} \varDelta _i e^{-(\varDelta _{i+1}/4)^{1/(r-1)}/6} \quad \le \quad 3(r-1) \varDelta (\log \log \varDelta ) e^{-(\varDelta _{\textsf{goal}}/4)^{1/(r-1)}/6}. $$

B Missing Proofs for the $\varTheta (\log ^* n)$ Algorithm and Lower Bound

We give two results on deterministic algorithms. Firstly, we give an $O\left( \log ^* n \right)$ rounds algorithm for $\tilde{O}\left( \varDelta ^{r/(r - 1)} \right)$-coloring any r-uniform hypergraph. Secondly, we complement this algorithm with a lower bound of $\varOmega \left( \frac{\log ^* n}{r} \right)$ on finding such a coloring.

1.1 B.1 Finding a $\tilde{O}\left( \varDelta ^{r/(r - 1)} \right)$-Coloring

In this section, we give a one round algorithm for transforming a strong $\tilde{O}(r^2 \varDelta ^2)$-coloring into a weak $\tilde{O}\left( r \cdot \varDelta ^{r/(r - 1)} \right)$-coloring for an r-regular hypergraph. This result can be viewed as an addendum to Linial’s algorithm for finding a $O(\varDelta ^2)$-coloring in $O(\log ^* n)$ rounds. This reduction is performed via a combinatorial argument extending the notion of a $\varDelta$-cover free family to an r-weak $\varDelta$-cover free family. Note that a $\tilde{O}(r^2\varDelta ^2)$ strong coloring can be found in $O(\log ^* n)$ rounds by using Linial’s algorithm on the underlying graph. In order to obtain such a coloring, it is useful to introduce r-weak $\varDelta$-cover free families of sets. This generalization of $\varDelta$-cover free families serves to relax coloring constraint to the problem of finding a weak coloring.

Definition 4

(r -weak $\varDelta$ -cover free families). Let $\mathcal {F}$ be a family of sets. The family $\mathcal {F}$ is a r-weak $\varDelta$-cover free family if, for every set $S_0 \in \mathcal {F}$, and $\varDelta$ subfamilies $\mathcal {S}_j = \lbrace S_{j,1}, \dots , S_{j,r-1} \rbrace \subseteq \mathcal {F}\setminus \lbrace S_0 \rbrace$, each of size $r-1$, the following holds:

$$ S_0 \not \subseteq \bigcup \limits _{j = 1}^{\varDelta } \bigcap \limits _{k = 1}^{r - 1} S_{j,k} $$

Note that a 2-weak $\varDelta$-cover free family is equivalent to the classical definition of an $\varDelta$-cover free family.

Lemma 13

(Lower bound on the size of r -weak $\varDelta$ -cover free families). For three integers $n, \varDelta , r \in \mathbb {N}$ such that $n \ge r \ge 2$ and $\varDelta \ge 1$, there exists an r-weak $\varDelta$-cover free family $\mathcal {F}$ of size n, where each $S \in \mathcal {F}$ is a subset of a ground set [m], $m = 5\lceil r \varDelta ^{r/(r - 1)} \ln (n) \rceil$.

Proof

In the proof that follows, we use that $e^{-s} \ge \left( 1 - \frac{s}{r} \right) ^r$ for all $1 \le s \le r$. For some m, consider a random collection $\mathcal {F} = \lbrace S_1,\ldots ,S_n \rbrace$ of subsets of [m] constructed the following way: for every element $x \in [m]$ and index $i \in [n]$, x belongs to $S_i$ with some fixed probability p, independently of every other pair $(x',i') \ne (x,i)$. For any given element x, index $i_0 \in [n]$, and $\varDelta$ sets of $r-1$ indices $\lbrace i_{j,1},\dots ,i_{j,r-1} \rbrace \subseteq [n]\setminus \lbrace i_0 \rbrace$, the probability of x being in the set $S_{i_0}$ but out of $\bigcup _{j = 1}^{\varDelta } \left( \bigcap _{k = 1}^{r - 1} S_{i_{j,k}} \right)$ is:

$$\begin{aligned} \Pr \left[ x \in S_{i_0} \setminus \bigcup _{j = 1}^{\varDelta } \left( \bigcap _{k = 1}^{r - 1} S_{i_{j,k}}\right) \right]&\ge \Pr \left[ x \in S_{i_0}\right] \left( 1 - \sum _{j = 1}^{\varDelta } \Pr \left[ x \in \bigcap _{k = 1}^{r - 1} S_{i_{j,k}}\right] \right) \\&= p(1-\varDelta p^{r-1}) \end{aligned}$$

Setting $p = (2\varDelta )^{-1/(r-1)}$, this probability is at least $\frac{1}{4\varDelta ^{1/(r-1)}}$. Therefore the probability that for every $x \in [m]$, $x \notin S_{i_0} \setminus \bigcup _{j = 1}^{\varDelta } \left( \bigcap _{k = 1}^{r - 1} S_{i_{j,k}} \right)$ is no more than $\left( 1 - \frac{1}{4\varDelta ^{1/(r - 1)}} \right) ^{m} \le e^{-m / (4\varDelta ^{1/(r - 1)})} \le n^{-5r\varDelta /4}$. The probability that valid multiset of indices $i_0, i_{1,1}, \dots , i_{\varDelta ,(r-1)}$ exists such that $S_{i_0} \subseteq \bigcup _{j = 1}^{\varDelta } \left( \bigcap _{k = 1}^{r - 1} S_{i_{j,k}} \right)$ is no more than $n^{(r - 1)\varDelta + 1} n^{-5 r \varDelta /4} < 1$. Therefore, an r-weak $\varDelta$-cover free family of n sets with no such indices exists.

Theorem 6. There is a deterministic $O(\log ^* n)$-round Congest algorithm to $O ( r \cdot \varDelta ^{r/(r - 1)} \log (r\varDelta ))$-color hypergraphs of maximum degree $\varDelta$ and rank r.

Proof

Let $\phi$ be a strong $O(r^2 \varDelta ^2)$-coloring of the graph, computed using Linial’s algorithm on the underlying graph. We show that $\phi$ can be converted in to a weak $\tilde{O}\left( r \cdot \varDelta ^{r/(r - 1)} \right)$-coloring in a single round. From Lemma 13, there must be an r-weak $\varDelta$-cover free family $\mathcal {F}$ of $O(r^2 \varDelta ^2)$ sets from a universe of $O(r \cdot \varDelta ^{r/(r - 1)} \log (r \varDelta ))$ elements. By indexing these sets in some universal order, each vertex v can choose the set $S_v$ at index $\phi (v)$. As the set is a member of $\mathcal {F}$, following Definition 4 there must exist at least one element $c_v \in S_v$, such that for every edge e incident to v, $c_v \notin \bigcap \limits _{u \in e \setminus \{v\}} S_u$. Therefore, coloring v with $c_v$, v can not be incident to any monochromatic edge. As computing the value of $c_v$ only requires the color of each neighbor in the $O(r^2 \varDelta ^2)$-coloring, this can be done in a single round from the $O(r^2 \varDelta ^2)$-strong coloring. Hence the total round complexity of this process is $O(\log ^* n)$, dominated by the process of finding the initial strong coloring. Further, as $c_v$ is selected from a universe of size $O(r \cdot \varDelta ^{r/(r - 1)} \log (r \varDelta ))$, the coloring of G from this process corresponds to a weak $O(r \cdot \varDelta ^{r/(r - 1)} \log (r \varDelta )) = \tilde{O}(r \cdot \varDelta ^{r/(r - 1)})$-coloring of G.

1.2 B.2 Lower Bounds on Finding Polynomial Colorings

We show that there exists a lower bound of $\varOmega \left( \frac{\log ^*n}{r} \right)$ for finding on finding a $\textrm{poly}(\varDelta )$-coloring, by generalizing the classic lower bound due to Linial [33]. Rather than using a simple n-cycle, we construct a strongly connected n-hyper-cycle. A strongly connected n-hyper-cycle with minimum rank r can be derived from an n-cycle C by constructing an edge for each connected component of size r in C. Note that the degree of a vertex in such a graph is $2 (r - 1)$. We provide a lower bound using this construction be reduction from the problem of $O(\varDelta ^c)$-coloring an n-cycle.

Theorem 7. For any pair of constants r and c, no Local algorithm can find a $O(\varDelta ^c / r)$ coloring of a rank r hypergraph in fewer than $\varOmega \left( (\log ^* n) / r\right)$ rounds.

Proof

For the sake of contradiction, let $\mathcal {A}$ be an algorithm that can weakly color a strongly connected n-hyper-cycle with $O(\varDelta ^c)$ colors for some pair of constants r and c. Let $T_\mathcal {A}$ be its complexity. Let $G = (V,E)$ be a cycle graph with n vertices. It is known that no algorithm can find a $O(\varDelta ^2)$-coloring on G in fewer than $\varOmega (\log ^* n)$ rounds. We show that an algorithm for coloring G in $O(T_\mathcal {A})$ rounds exists, implying the lower bound on $T_\mathcal {A}$.

Let $G' = (V, H)$ be an r-uniform hypergraph constructed from G, with edge set $H = \{(v_1, \ldots , v_r) \in V^r \mid (v_i,v_{i + 1}) \in E, \forall i \in 1,2,\ldots ,r - 1 \}$. Note that $G'$ corresponds to a strongly connected n-cycle. Observe that any algorithm on $G'$ can be simulated on G in at most a factor of r additional rounds. Let $\phi$ be the coloring on V after running $\mathcal {A}$. Given any vertex $v \in V$, let $h_1,h_2 \in H$ be the pair of hyperedges incident to v such that $N(v) = h_1 \cup h_2$. In other words, $h_1$ and $h_2$ are the hyperedges that include v and the two vertices at a distance of $r - 1$ from v in G. As $\phi$ is a weak coloring of $G'$, there must exists two vertices $u_1,u_2 \in h_1 \times h_2$ such that $\phi (v) \not \in \lbrace \phi (u_1),\phi (u_2) \rbrace$.

Let $C = (V', E')$ be a connected component in G such that $\forall v,u \in V', \phi (v) = \phi (u)$. Following the above observation, the maximum length of such a component is $2r - 3$. As the number of colors assigned by $\phi$ is at most $O(r^c)$ for some pair of constants r and c, $\phi$ can be turned into a proper coloring of G by going through each color class and coloring the nodes in each component in order of decreasing ID. Therefore $\phi$ can be transformed into a proper coloring of G in at most $O(r^{c+1})$ rounds, and hence $r\cdot (T_\mathcal {A}+ O(r^{c+1})) \in \varOmega (\log ^*n)$, i.e. $\mathcal {A}$ must take at least $\varOmega \left( \log ^* n \right)$ rounds, since r and c are constants.

Note that the hypergraph used for the lower bound is not linear, i.e., the theorem does not rule out the existence of an $o(\log ^* n)$ round algorithm whose scope is limited to linear hypergraphs.