Distributed $\mathbf{(}𝚫\mathbf{+}\mathrm{𝟏}\mathbf{)}$-Coloring in Graphs of Bounded Neighborhood Independence

In Section 2, we give a highlevel description of all our technical steps that are needed to prove Theorems 1 and 2. The algorithm that leads to the upper bound of Theorem 1 is a recursive algorithm. The recursive subproblems are defined in Section 2.2. The recursive structure consists of two main steps, slack generation and color space reduction, which are described in Sections 2.3 and 2.4, respectively. At the core of the color space reduction part is an algorithm to efficiently compute list defective colorings in graphs with small neighborhood independence by using an efficient algorithm to compute good quality list arbdefective colorings (definitions, see below). Section 2 is concluded with Section 2.6, which describes the highlevel ideas of the lower bound result given by Theorem 2. The technical details of the paper appear in three sections. Sections 3 and 4 contain the main technical contributions of the paper, the details on how to get from list arbdefective to list defective colorings and the recursive structure and analysis of our main algorithm. The technical details on slack generation (Appendix A), color space reduction (Appendix B) are adaptations of existing techniques and they therefore appear in the appendix. The formal proof of the lower bound is deferred to Section 5 of the full version [26] of this work.

Defective colorings are a key tool that is used in essentially all modern deterministic distributed coloring algorithms. In its most standard form, for an integer parameter $d\ge 0$, a $c$-coloring of the nodes of a graph $G=(V,E)$ is called $d$-defective if each node has at most $d$ neighbors of the same color. Defective colorings have been used to decompose a given graph into a small number of subgraphs of smaller degree that can then be colored more efficiently either in parallel (e.g., [7, 4, 10, 11, 13, 38, 31]) or sequentially (e.g., [10, 11, 13, 17, 23, 38, 31]). Although defective coloring might seem to be a simple relaxation of proper graph coloring, it is algorithmically quite different. While it is known that every graph has a $d$-defective coloring with $\lceil \frac{\mathrm{\Delta }+1}{d+1}\rceil$ colors [42], for general values of $d$, there is no $f(\mathrm{\Delta })\cdot {\log }^{\ast }n$-round distributed algorithm known to compute a $d$-defective coloring even with $O(\mathrm{\Delta }/d)$ colors. The only such algorithm known is an $O({\log }^{\ast }n)$-round algorithm to compute a $d$-defective coloring with $O\left({\left(\frac{\mathrm{\Delta }}{d+1}\right)}^2\right)$ colors [37]. Since we use a variant of this algorithm as a tool in our algorithm, we state it formally.

Usually, when computing a $(\mathrm{\Delta }+1)$-coloring, this is done in several phases. One starts with all nodes being uncolored and in each phase, a given partial proper coloring of the nodes is extended by coloring some of the previously uncolored nodes. When solving $(\mathrm{\Delta }+1)$-coloring in this way, the problem that needs to be solved in each step is a list coloring problem or more precisely a $(\mathrm{𝑑𝑒𝑔𝑟𝑒𝑒}+1)$-list coloring problem: Each node $v$ is initially given a list $L_v$ of available colors and in the end, the nodes have to be colored properly such that each node $v$ is colored with a color from its list $L_v$. In a $(\mathrm{𝑑𝑒𝑔𝑟𝑒𝑒}+1)$-list coloring instance, the list $L_v$ of each node $v$ is of size $|L_v|\ge \mathrm{deg}(v)+1$. The notion of defective coloring has been extended to list colorings implicitly in [38] and explicitly in [24]. Formally, in list defective coloring, each node $v$ obtains a color list $L_v$ together with a defect function $d_v:L_v\to {\mathbb{N}}_0$ that assigns non-negative integer values to the colors in $L_v$. The coloring has to assign a color $x_v\in L_v$ to each node $v$ such that the number of neighboring nodes $u$ that get assigned color $x_u=x_v$ is at most $d_v(x_v)$. While standard defective colorings can be used to recursively divide non-list coloring instances, list defective colorings can be used to recursively divide list coloring instances (for details, see the discussion on color space reduction below).

Finally, we need to define the notion of arbdefective colorings, which was introduced in [11]. In [11], a $d$-arbdefective $c$-coloring of a graph was defined as a coloring of the nodes with $c$ colors such that the graph induced by each color class has arboricity at most $d$. We use a slightly different definition, which is locally checkable and which has turned out to be algorithmically more covenient (see, e.g., [12, 15, 38, 3]). We define a $d$-arbdefective $c$-coloring of a graph as a $c$-coloring of the nodes together with an orientation of the monochromatic edges so that every node has at most $d$ outneighbors of the same color. We further note that this only guarantees that each color class has pseudoarboricity at most $d$ (and thus arboricity at most $d+1$). One could strengthen the definition to imply arboricity at most $d$ by requiring the edge orientation of each color class to be acyclic. We do not need to make this additional restriction.

List arbdefective colorings are defined in the natural way: Each node $v$ must be colored with a color $x_v$ from its list $L_v$, the monochromatic edges are oriented such that $v$ has at most $d_v(x_v)$ outneighbors of color $x_v$. Unlike standard defective colorings, $d$-arbdefective colorings with $\lceil \frac{\mathrm{\Delta }+1}{d+1}\rceil$ colors can be computed by a simple sequential greedy algorithm and as a result, efficient distributed arbdefective coloring algorithms with a small number of colors are known. In particular, in [15], it is shown that a $d$-arbdefective coloring with $O(\mathrm{\Delta }/d)$ colors can be computed deterministically in $O(\mathrm{\Delta }/d+{\log }^{\ast }n)$ rounds. The main reason why for graphs of bounded neighborhood independence, we have faster deterministic coloring algorithms than for general graphs, is the following observation, which was first made in [12]. If $G$ is a graph with neighborhood independence $\theta$, then any $d$-arbdefective coloring of $G$ at the same time is a $(2d+1)\cdot \theta$-defective coloring of $G$. For graphs of bounded neighborhood, we therefore have efficient algorithms to compute $d$-defective colorings with $O(\mathrm{\Delta }/d)$ colors. All the fast $f(\mathrm{\Delta })+O({\log }^{\ast }n)$-round coloring algorithms that specifically work for families of graphs with bounded neighborhood independence are in particular based on this fact [12, 38, 7, 4].

We conclude this short discussion of defective colorings with the following notion of slack, which specifies how loose a given list defective or list arbdefective coloring instance is.

First note that list arbdefective coloring generalizes $(\mathrm{\Delta }+1)$-list coloring in the following way. First note that $(\mathrm{\Delta }+1)$-coloring is clearly a special case of the $(\mathrm{𝑑𝑒𝑔𝑟𝑒𝑒}+1)$-list coloring problem. Further, if every node $v$ is given a list $L_v$ of colors and the allowed defect or arbdefect for every $v\in V$ and every $x\in L_v$ is set to $d_v(x)=0$, then the given list defective or list arbdefective coloring instance is a standard list coloring instance. The instance corresponds to a $(\mathrm{𝑑𝑒𝑔𝑟𝑒𝑒}+1)$-list coloring instance if and only if its slack is at least $1$. If we have an algorithm to solve list arbdefective coloring instances with slack $1$, we can therefore use this algorithm to solve $(\mathrm{𝑑𝑒𝑔𝑟𝑒𝑒}+1)$-list coloring instances and thus also to solve $(\mathrm{\Delta }+1)$-coloring.

Our algorithm to achieve the upper bound of Theorem 1 is a recursive algorithm to solve list arbdefective coloring instances. As part of the recursive structure, we also solve some list defective coloring instances. Both problems, we parameterize by two quantities: the slack $S$ (as given by Definition 4) and the size of the color space $C$. The size of the color space is equal to $C$ if all the color lists $L_v$ of the nodes are composed of colors from a set of size $C$ (e.g., if the lists only use colors $1,\mathrm{\dots },C$). For the remainder of the analysis, we use the following notation.

We use $P_A(S,C)$ to denote the family of list arbdefective coloring instances with slack at least $S$ and with a color space of size at most $C$. Similarly, we use $P_D(S,C)$ to denote the corresponding list defective coloring problems. Recall that we defined (list) arbdefective coloring to be a coloring of the nodes together with an orientation of the monochromatic edges. Solving an instance of $P_A(S,C)$ therefore means to compute the coloring and the required edge orientations. The optimal round complexities of solving problems of the form $P_A(S,C)$ and $P_D(S,C)$ deterministically in the $\mathrm{𝖫𝖮𝖢𝖠𝖫}$ model are denoted by $T_A(S,C)$ and $T_D(S,C)$, respectively. Before continuing with the discussion of how we solve $P_A(S,C)$ and $P_D(S,C)$, we make a remark regarding the parameterization by the slack $S$ and the color space size $C$. Typically, the parameterization of both the number of allowed colors and the time complexity of local coloring problems is mostly done as a function of the maximum degree $\mathrm{\Delta }$ of the graph. Naturally, the time complexity as a function of $\mathrm{\Delta }$ decreases if the number of available colors increases as a function of $\mathrm{\Delta }$. Consider the problem of coloring with $f(\mathrm{\Delta })\ge \mathrm{\Delta }+1$ colors. In this case (if we do not consider list coloring), the size of the color space is $C=f(\mathrm{\Delta })$ and the slack is $S=f(\mathrm{\Delta })/(\mathrm{\Delta }+1)$. For any of the standard coloring problems, parameterization by $S$ and $C$ thus directly implies a parameterization of both the number of colors and time complexity as a function of $\mathrm{\Delta }$.

Note that in general $P_A(S,C)$ is an easier problem than $P_D(S,C)$, i.e., we have for any $S$ and $C$. Any solution to $P_D(S,C)$ automatically also is a solution to $P_A(S,C)$, even with an arbitrary orientation of the edges.⁵⁵5In some cases, it is also known that $P_D(S,C)$ is strictly harder than $P_A(S,C)$ [6]. Further, as already remarked above, if we have $d_v(x)=0$ for all $v\in V$ and all $x\in L_v$, then both $P_D(S,C)$ and $P_A(S,C)$ are equivalent to the standard proper list coloring problem with lists $L_v$ of size $|L_v|>S\cdot \mathrm{deg}(v)$. The highlevel recursive structure of our algorithm is depicted in Figure 1. In the following, we briefly describe each of the steps.

List coloring problems naturally become easier if the color lists and thus the slack of the problem gets larger. A simple way to generate slack is the following. Starting from a problem with small slack, use some defective coloring to divide the graph into several parts of significantly smaller degree. Now, when only coloring one of the parts, but using the full list of colors, the slack of the instance to solve is much larger. If we have a list coloring algorithm, we can sequentially go through the different parts and color them. This method has first been introduced in [9] and it has subsequently been optimized and used in [23, 38, 7, 24]. This technique can not only be applied to standard list coloring, but also to the more general list arbdefective coloring problem $P_A(S,C)$, i.e, one can solve a list arbdefective coloring instance $P_A(S,C)$ by iteratively solving several instances of $P_A(S^{\prime },C)$ for $S^{\prime }>S$. If we use the defective coloring algorithm of [37] and if the initial slack is $S\ge S_0$ for some constant $S_0>1$, the number of required slack $S^{\prime }$-instances is $O(S^{\prime 2})$. If the initial slack is $S=1$, the method only allows to reduce the maximum uncolored degree by some constant factor and one has to repeat the whole process $O(\log \mathrm{\Delta })$ times to fully color the graph. The number of slack $S^{\prime }$-instances therefore becomes $O(S^{\prime 2}\cdot \log \mathrm{\Delta })$ in this case. This slack generation technique is formally stated in the following lemma, which is proven in Appendix A. In our algorithm, we use the technique to first reduce $P_A(1,C)$ to $O(\log \mathrm{\Delta })$ instances of $P_A(2,C)$ and we then solve $P_A(2,C)$ recursively.

List defective coloring was originally introduced in [38, 24] as a natural problem to recursively reduce the color space of a list (arbdefective) coloring problem. In the second step, we use exactly this idea to a given instance of list arbdefective coloring $P_A(S,C)$. We partition the color space of size $C$ into $C^{\epsilon }$ parts of size $C^{1-\epsilon }$ for some suitably chosen (in this overview, we for simplicity assume that $C^{\epsilon }$ and $C^{1-\epsilon }$ are integers). The partition of the color space is done in an arbitrary way. We then assign each node $v$ to one of the $C^{\epsilon }$ color subspaces. When doing this, the color list $L_v$ of node $v$ (of the list arbdefective coloring problem that we have to solve) is restricted to only the colors in the chosen color space. For the assignment of nodes to color subspaces, we set up a list defective coloring problem instance $P_D(\mathrm{\Theta }(\theta ),C^{\epsilon })$. In this list defective coloring instance, the allowed defect for a node $v$ when choosing some color subspace is proportional to the sum of the arbdefects $d_v(x)$ of $v$ (in the given list arbdefective coloring problem $P_A(S,C)$ that we need to solve) corresponding to colors $x\in L_v$ that are in the given color subspace. This results in $C^{\epsilon }$ instances of $P_A(2,C^{1-\epsilon })$ that operate on disjoint color spaces and can therefore be solved in parallel. The slack $S$ of the original list arbdefective coloring problem has to be chosen sufficiently large to compensate for the loss in slack in this partitioning step (which is equal to the slack of the defective coloring instance that we use to divide the color space). This color space reduction step is formally done in Lemma 6, which appears in Appendix B. The choice of $\epsilon$ depends on the value of the neighborhood independence $\theta$, for our main result, we either choose $\epsilon =1/2$ (if $\theta$ is large) or $\epsilon =\mathrm{\Theta }(\log \log \log \mathrm{\Delta }/\log \log \mathrm{\Delta })$ (if $\theta$ is small). If $\theta$ is small, the time that we need to compute the list defective coloring to divide the color space is more significant than the loss in slack in this step. At the cost of having a somewhat larger recursion depth, we can make this step more efficient by choosing $\epsilon$ and thus $C^{\epsilon }$ small. The list defective coloring instance to assign the color subspaces then itself has a smaller color space over which it operates. The details are given by the following lemma, which is proven in Appendix A.

The last step is the only one that requires small neighborhood independence and it is the main technical contribution towards proving Theorem 1. As mentioned in Section 2.1, in graphs of neighborhood independence $\theta$, any $d$-arbdefective coloring is also a $(2d+1)\cdot \theta$-defective coloring. The reason is as follows. Assume that in a given $d$-arbdefective coloring, some node $v$ is assigned color $x$ and let $A$ be the set of neighbors of $v$ that are also colored with color $x$. Because in a $d$-arbdefective coloring, all monochromatic edges are oriented and any node has at most $d$ outneighbors of the same color, the subgraph induced by $A$ is an oriented graph with outdegree at most $d$. This subgraph can therefore be colored with at most $2d+1$ colors. Because the neighborhood independence of our graph is at most $\theta$ and because all nodes in $A$ are neighbors of a single node (of $v$), any independent set of $G[A]$ has size at most $\theta$. Hence, we have $|A|\le (2d+1)\cdot \theta$. By using the arbdefective coloring algorithm of [15], a $(d/(2\theta )-1/2)$-arbdefective coloring with $O(\mathrm{\Delta }\theta /d)$ colors and thus a $d$-defective coloring with $O(\mathrm{\Delta }\theta /d)$ colors can be computed in $O(\mathrm{\Delta }\theta /d+{\log }^{\ast }n)$ rounds.

In this paper, we extend this idea to the list versions of the problems. That is, in graphs of small neighborhood independence, our goal is to use an algorithm for computing list arbdefective colorings to solve some given list defective coloring instance (with larger slack). The main challenge to achieve this is that in list defective colorings, different nodes can have different defects for the same colors. This means that in the above argument, the nodes in the set $A$ could use much larger defects for color $x$ and they could therefore have much larger outdegrees than what $v$ uses for color $x$. As a result, we unfortunately cannot set up a single list arbdefective coloring instance to solve a given list defective coloring instance. The problem is relatively easy to overcome if for each node $v$, $v$ uses approximately the same defect for all the colors in its color list $L_v$. One can then iterate over $O(\log \mathrm{\Delta })$ defect classes (starting with large defects) and only color the nodes that use approximately the same defects in a single list arbdefective coloring instance. Because when $v$ gets its color, the neighbors that use larger defects have already been colored, $v$ can control the number of such neighbors that have the same color. One can enforce that the defects of all colors in the list of a node $v$ are equal by sacrificing an $O(\log \mathrm{\Delta })$-factor in the slack of the problem (each node only keeps the colors for one of the defect classes).

In order to avoid the additional $\mathrm{\Theta }(\log \mathrm{\Delta })$ factor in the slack of the list defective coloring, we extend this approach by combining it with the general idea of slack generation as described in Section 2.3. We can temporarily increase the slack by an $O(\log \mathrm{\Delta })$ factor by using the defective coloring algorithm of [37] to divide the graph into $\mathrm{\Theta }({\log }^2\mathrm{\Delta })$ subgraphs in which the degree of each node is by an $\mathrm{\Omega }(\log \mathrm{\Delta })$ factor smaller. Note however that if we do not have the additional $O(\log \mathrm{\Delta })$ factor in the slack, but if we nevertheless just keep one defect class in each list, the slack of the actual instance to solve still becomes smaller than $1$. We therefore still have to use the full list. We can however show that by iterating over the $O(\log \mathrm{\Delta })$ defect classes and over the subgraphs of the smaller degrees for each defect class, for each node, the slack becomes large enough in one of the $O(\log \mathrm{\Delta })$ iterations where we consider the node. This allows to solve a single list defective coloring instance $P_D(O(\theta ),C)$ by iteratively solving $O({\log }^3\mathrm{\Delta })$ list arbdefective coloring instances $P_A(2,C)$. This is formally stated in the following theorem, whose proof appears in Section 3.

The proof of Theorem 2 builds on a lower bound argument of [6]. There, it is shown that computing a $(d-2)$-defective $2$-coloring in $d$-regular trees requires $\mathrm{\Omega }(\log n)$ deterministic rounds. The core idea is a reduction from the sinkless orientation problem in $2$-colored regular bipartite graphs, which itself has a deterministic $\mathrm{\Omega }(\log n)$ lower bound [18]. Our contribution is to extend this reduction to defective $2$-edge colorings of hypergraphs of small rank $r$ (or equivalently, to $2$-defective vertex colorings of line graphs of rank-$r$ hypergraphs).

The argument in [6] relies on the complexity classification of LCL problems in bounded-degree graphs [19]: every such problem either requires $\mathrm{\Omega }(\log n)$ deterministic rounds or can be solved deterministically in time $O({\log }^{\ast }n)$. In the latter case, one first computes a proper distance-$k$ coloring with $O(1)$ colors for some (problem-dependent) constant $k$. Afterwards the problem can be solved in $O(1)$ rounds by just using those colors and without using unique IDs. To rule out the $O({\log }^{\ast }n)$ case for $(d-2)$-defective $2$-coloring in $d$-regular trees, one can thus assume the existence of a constant-time algorithm that works given such a distance-$k$ coloring and lead this to a contradiction.

The reduction proceeds as follows. For a given $\mathrm{\Delta }$-regular $2$-colored graph $G$, where $\mathrm{\Delta }=d{(d-1)}^{2k-1}$, we first replace each edge with two half-edges. Each node with its $\mathrm{\Delta }$ incident half-edges is then replaced by a $d$-regular tree of height $2k$ whose leaves correspond to the half-edges. When two nodes $u,v$ are connected in $G$, we merge the corresponding leaves in their trees and add some additional edges to restore degree $\mathrm{\Delta }$. This yields a graph where all nodes have degree $d$ or $1$, and on which we can run the assumed $(d-2)$-defective $2$-coloring algorithm (say with colors black and white). By controlling the distance-$k$ coloring, one can enforce that all nodes on one side of the bipartition of $G$ output black and the nodes on the other side output white. If a $d$-regular tree is complete up to some even distance $2\mathrm{\ell }$ from the root, one can show that in any valid $(d-2)$-defective $2$-coloring, one of the nodes at distance $2\mathrm{\ell }$ must have the same color as the root. Because the leaf nodes of the $d$-regular trees of height $2k$ from both sides are merged and the roots on the two sides use opposite colors, this implies that each root nodes sees both colors among the nodes at distance $2k$. On the original $\mathrm{\Delta }$-regular bipartite graph, this induces a $2$-coloring of the edges such that each node is incident to edges of both colors and in $2$-colored bipartite graphs, such an edge coloring is equivalent to a sinkless orientation, completing the reduction.

To adapt this to hypergraphs of rank $r$, we use the standard representation of a $d$-regular rank-$r$ hypergraph as a biregular bipartite graph: degree-$r$ nodes correspond to hyperedges, and degree-$d$ nodes to original vertices. A $\delta$-defective edge-coloring of the hypergraph then corresponds to coloring the degree-$r$ nodes such that for each such node, at most $\delta$ of the degree-$r$ nodes at distance two share the same color. In the reduction, each node with $\mathrm{\Delta }$ half-edges is replaced by a $(r,d)$-biregular tree of height $4k$, rooted at a degree-$r$ node. In such trees, every degree-$r$ node has $r(d-1)$ degree-$r$ nodes at distance two, of which at least $d$ must have the opposite color if the defect is bounded by $r(d-1)-d$. Because in a rooted $(r,d)$-biregular tree, each degree-$r$ node has only $d-1$ nodes at distance $2$ that are either closer to or equally far from the root, at least one node with the opposite color must be one of the children’s children. This guarantees that at every fourth level, some node shares the root’s color. By ensuring opposite root colors for the two sides of the bipartition, the same argument as before induces an edge coloring of the bipartite graph with $2$ colors that forces both colors at every node – again equivalent to a sinkless orientation. The full proof can be found in Section 5 of the full verison [26].