On the Complexity of Distributed Edge Coloring and Orientation Problems

Since the publication of [44], researchers have made astonishing progress in understanding the distributed complexity of solving LCL problems in the $\mathrm{𝖫𝖮𝖢𝖠𝖫}$ model¹¹1In the $\mathrm{𝖫𝖮𝖢𝖠𝖫}$ model [45], the nodes of a graph can exchange messages of arbitrary size over the edges of the graph in synchronous rounds. For a formal definition, we refer to Section 2. and in related models. Apart from studying the complexity of specific problems (see, e.g., [8, 13, 30, 43, 41, 32, 24, 40, 42, 9] for a small selection), there also is substantial work on establishing the landscape of possible LCL complexities [5, 7, 6, 17, 20, 29, 25, 18, 36] and also towards understanding the task of deciding if a given LCL problem belongs to a certain complexity class [2, 18, 14, 4, 44, 3]. For general bounded-degree graphs, we know that the deterministic $\mathrm{𝖫𝖮𝖢𝖠𝖫}$ model complexity of LCL problems is either $O(1)$, in the range $\mathrm{\Omega }(\log {\log }^{\ast }n)$–$O({\log }^{\ast }n)$, or in the range $\mathrm{\Omega }(\log n)$–$O(n)$. By using techniques of [44], Chang and Pettie [20] observed that there cannot be any LCL problem with a (deterministic or randomized) complexity in the range $\omega (1)$–$o(\log {\log }^{\ast }n)$. Further, Chang, Kopelowitz, and Pettie [17] proved that there cannot be any deterministic complexities between $\omega ({\log }^{\ast }n)$ and $o(\log n)$. It has further been shown in [5, 7] that the complexity landscape in the range $\mathrm{\Omega }(\log n)$–$O(n)$ is dense, i.e., there are no further gaps. In bounded-degree trees, the landscape is even more sparse. In this case, the possible deterministic LCL complexities are $\mathrm{\Theta }(1)$, $\mathrm{\Theta }({\log }^{\ast }n)$, $\mathrm{\Theta }(\log n)$, and $\mathrm{\Theta }(n^{1/k})$ for every integer $k\ge 1$ [20, 36, 3]. In bounded-degree trees, it is further known that for problems of complexity $\mathrm{\Omega }(\log n)$, determining the exact asymptotic complexity of a given problem is decidable [18].

Understanding the role and power of randomness in the context of distributed LCL problems has been a major objective of the research in the area (see, e.g., [25, 17, 20, 29, 10, 6, 31] for papers that explicitly deal with this topic). As many LCL problems require some kind of local symmetry breaking, the use of randomness in distributed LCL algorithms is often quite natural. Recently, a series of papers [25, 29, 27, 28, 26, 46] established generic derandomization techniques that allow to turn any $T$-round randomized $\mathrm{𝖫𝖮𝖢𝖠𝖫}$ algorithm for an LCL problem into a $T\cdot \tilde{O}({\log }^{2}n)$-round deterministic $\mathrm{𝖫𝖮𝖢𝖠𝖫}$ algorithm.²²2We use $\tilde{O}(x)$ to denote expressions that are upper bounded by $x\cdot \text{poly}\log x$. Using randomization can therefore not gain more than a factor of $\tilde{O}({\log }^{2}n)$. It is further known that for LCL problems of complexity $O({\log }^{\ast }n)$, randomization does not help. There is however one important class of problems for which randomization provably helps exponentially. It was shown in [13, 34, 17] that computing a sinkless orientation of the edges of a bounded-degree graph requires $\mathrm{\Theta }(\log n)$ rounds deterministically and $\mathrm{\Theta }(\log \log n)$ rounds with randomization. Interestingly, this is a more general phenomenon. As shown in [20], on bounded-degree graphs, every randomized LCL algorithm with a round complexity of $o(\log n)$ can be sped up to run in the time required to solve an instance of the constructive Lovász Local Lemma (LLL) problem with a polynomial LLL criterion (cf. Section 2). The randomized LLL round complexity is currently known to be $\tilde{O}({\log }^4\log n)$. We therefore know that any randomized $o(\log n)$-round LCL algorithm can be sped up to run in $\tilde{O}({\log }^4\log n)$ rounds. It is further known that any randomized $o(\log \log n)$-round LCL algorithm can be sped up to run in $O({\log }^{\ast }n)$ rounds deterministically [17]. We therefore know that there is a class of problems that can be solved by using LLL algorithms that have polylogarithmic deterministic complexity and that have randomized complexity $\tilde{O}({\log }^4\log n)$. In bounded-degree trees, it is even known that the complexity of the constructive LLL problem is exactly $\mathrm{\Theta }(\log \log n)$. Hence, in bounded-degree trees, some of the problems that can be solved in $\mathrm{\Theta }(\log n)$ rounds deterministically can be solved in $\mathrm{\Theta }(\log \log n)$ rounds with randomization and in the case of bounded-degree trees, these also are the only problems for which randomization helps. While we know that the randomized LLL complexity class exists, we do not yet have a thorough understanding of which problems belong to this family, not even for simple families of LCL problems in bounded-degree trees, raising the following important question.

It seems likely that providing a full characterization (i.e., designing an algorithm that decides for every LCL problem whether it can be solved with randomization in $o(\log n)$ rounds or requires $\mathrm{\Omega }(\log n)$ rounds), if possible at all, will require a structured research program as such questions are notoriously hard.³³3For instance, it is not even known whether it is decidable whether a given LCL problem can be solved in constant time on bounded-degree trees. We make first progress towards this goal by providing such characterizations for some of the most fundamental problem classes amongst LCL problems exhibiting deterministic complexities of $\mathrm{\Omega }(\log n)$ rounds. Note that a variety of classic LCL problems, such as $(\mathrm{\Delta }+1)$-coloring, $(2\mathrm{\Delta }-1)$-edge coloring, maximal matching or maximal independent set, can be solved in $O({\log }^{\ast }n)$ rounds on constant-degree graphs [35], and therefore do not fall into the class of $\mathrm{\Omega }(\log n)$-round problems. Instead, the typical problems considered in the literature that fall in the deterministic $\mathrm{\Omega }(\log n)$-regime are splitting problems (which form the heart of classic divide-and-conquer approaches for solving other LCLs), which encompass both orientation and coloring problems. In their standard form, splitting problems fall into the class of so-called binary labeling problems – a class that has been instrumental in the context of complexity classification, including (efficient) decidability, in the deterministic setting [4]. Even restricted to binary labeling problems, the task of deciding between sublogarithmic and (at least) logarithmic randomized complexity is a major open problem on the path towards understanding randomness for LCL problems.

In an attempt towards exactly characterizing the distributed complexities of all problems in a large class of LCL problems, the authors of [4] considered the class of binary labeling problems in the edge labeling formalism [12]. In this formalism, labels have to be assigned to the edges of a two-colored bipartite graph. For each side of the bipartite graph, the valid configurations are given by a set of allowed multisets of edge labels. The standard way to use this framework in general graphs is to consider the bipartite graph between nodes and edges. Each of the original nodes of a graph $G=(V,E)$ is colored white and in the middle of each edge $e\in E$, we place an additional black node. Each edge $e=\{u,v\}\in E$ is then split into two half-edges $(u,e)$ and $(v,e)$. The labels are placed on the half-edges and the validity of a labeling is determined by the allowed white node configurations and the allowed black edge configurations. The binary labeling problems are all problems that can be expressed with only two different labels (we call them red ($𝖱$) and blue ($𝖡$) in the following) in the edge labeling formalism. In the graph setting with labels on half-edges, binary labeling problems correspond to edge orientation and edge $2$-coloring problems. If the allowed edge configurations are $\{𝖱,𝖱\}$ and $\{𝖡,𝖡\}$, we get problems where the edges of a graph need to be colored red and blue. If the only allowed edge configuration is $\{𝖱,𝖡\}$, we get problems where all edges need to be oriented and if the allowed edge configurations are $\{𝖱,𝖱\}$ and $\{𝖱,𝖡\}$, we get problems where we need to compute a partial orientation of the edges. All other combinations are symmetric or they lead to trivial cases.

In [4], the deterministic complexity of all binary labeling problems in the general edge labeling formalism in biregular bounded degree trees⁴⁴4More concretely, for two constants $d$ and $\delta$, it is assumed that the bipartite graph is properly colored with colors white and black and that all white nodes have degree $d$ and all black nodes have degree $\delta$. Note that when labeling half-edges in $\mathrm{\Delta }$-regular general graphs, we have $d=\mathrm{\Delta }$ and $\delta =2$. was exactly characterized. We thus have an exact characterization of the deterministic complexity of all LCLs in regular bounded-degree trees that either require to color the edges with two colors or to (partially) orient the edges. In [4], the authors also already prove some initial results on the randomized complexity of binary labeling problems. However, as pointed out above, classifying the randomized complexity of those problems is still largely open and our results can be seen as a step towards closing this gap. We in particular give an exact characterization of the randomized complexity of solving arbitrary edge $2$-coloring problems in regular bounded-degree trees.

A special and important case of binary labelings are balanced oriented and unoriented degree splittings. Unoriented degree splittings are colorings of the edges with two colors such that every node $v$ is incident to approximately $\mathrm{deg}(v)/2$ edges of each color. An oriented degree splitting is an orientation of the edges so that for every node, indegree and outdegree are approximately equal. Degree splitting problems are not only natural to study, but also serve as key tools in other distributed tasks. Such problems lie at the heart of distributed divide-and-conquer algorithms and variants of splitting have in particular enabled efficient edge-coloring algorithms. In [34, 30], splitting was used to obtain the first deterministic polylog-time edge coloring algorithm that uses only by a $(1+o(1))$-factor more colors than the commonly considered $2\mathrm{\Delta }-1$ colors (thereby solving a long-standing open problem from the 90s). In [33], splitting is even used to obtain edge colorings with only $(1+o(1))\mathrm{\Delta }$ colors. Also, recent work on hypergraph sinkless orientation [16] (which is a weak form of degree splitting) improved edge coloring and already inspired further follow-ups [37, 38]. Since our results provide stronger splitting guarantees, we expect them to similarly facilitate future advances, especially for randomized algorithms where previous progress has been limited. The distributed computation of degree splittings was in particular studied in [34, 30]. In [30] it was shown that one can compute both versions of degree splitting with constant discrepancy in time $\tilde{O}(\mathrm{\Delta })\cdot \log n$ deterministically and in time $\tilde{O}(\mathrm{\Delta })\cdot \log \log n$ randomized. The discrepancy is the maximum absolute difference between the two kinds of edges at any node. For oriented degree splitting, it was even shown that for odd-degree nodes, a discrepancy of $1$, and for even-degree nodes, a discrepancy of $2$ can be achieved. We improve the algorithm of [30] and we show that also for unoriented degree splitting, the same discrepancy as for oriented degree splitting can be achieved.

For a (multi)graph $G=(V,E)$ and a node $v\in V$, we use $d_G(v)$ to denote the degree of $v$ (in the case of a multigraph, the number of incident edges of $v$). Whenever $G$ is clear from the context, we write $d(v)$ instead of $d_G(v)$. Further, whenever $G$ denotes the communication graph and $G$ is clear from the context, we use $n$ to denote the number of nodes of $G$ and $\mathrm{\Delta }$ to denote the maximum degree of $G$.

In the $\mathrm{𝖫𝖮𝖢𝖠𝖫}$ model [43, 45], the nodes of an $n$-node graph $G=(V,E)$ communicate in synchronous rounds over the edges of $G$. The nodes are equipped with unique $O(\log n)$-bit IDs and in each round, each node $v\in V$ can perform some arbitrary internal computation, send a message of arbitrary size to each neighbor, and receive the messages sent to it by its neighbors. The time (or round) complexity of an algorithm is defined as the maximum number of rounds required for all nodes to terminate. The time complexity is typically expressed as a function of global network parameters such as $n$ or the maximum degree $\mathrm{\Delta }$. We assume that those global parameters are known to the nodes of $G$.⁵⁵5This assumption can usually be dropped or at least significantly relaxed by only requiring the knowledge of some approximations of the parameters (see, e.g., [39]).

As described in Section 1.1, our algorithms use the following three subroutines in our algorithms.

• $\mathrm{■}$

  Sinkless Orientation: The sinkless orientation problem on an $n$-node multigraph $G=(V,E)$ asks for an orientation of the edges $E$ such that every node $v\in V$ of degree $\ge 3$ has at least one outgoing edge. It was shown in [34, 30] that the sinkless orientation can be solved in $O(\log n)$ rounds deterministically and in $O(\log \log n)$ rounds with randomization.

• $\mathrm{■}$

  Balanced Orientation: The problem of computing a balanced orientation of an $n$-node multigraph $G=(V,E)$ asks for an orientation of the edges $E$ such that every node $v\in V$ has outdegree $\in [d(v)/2-1,d(v)/2+1]$. If $\mathrm{\Delta }$ is the maximum degree of $G$, it is shown in [30] that a balanced orientation can be computed in time $O(\mathrm{\Delta }\cdot \log \mathrm{\Delta }\cdot {\log }^{1.71}\mathrm{\Delta })\cdot {𝖳}_{\mathrm{𝖲𝖮}}$.

• $\mathrm{■}$

  Constructive LLL: The Lovász Local Lemma (LLL) considers the following setting. A set $V_H$ of (bad) events that are defined as functions over some underlying product probability space. Let $H=(V_H,E_H)$ be the conflict graph of those events, i.e., $H$ contains an edge between two events iff they are dependent (i.e., if they depend on intersecting sets of random variables in the underlying product space). The LLL states that if the maximum degree of $H$ is $d$ and the probability of each event is upper bounded by $p$ such that $ep(d+1)\le 1$, then the probability that none of the events occurs is positive. The instance is said to have a polynomial LLL criterion if $p\le d^{-\gamma }$ for a constant $\gamma >0$. If $\gamma$ is a sufficiently large constant, there are efficient distributed algorithms to determine a setting for the underlying random variables that avoids all the bad events. The best known round complexities for those algorithms are $O(\log n)$ for deterministic algorithms in tree-like dependency graphs [19], $O(\log \log n)$ for randomized algorithms in tree-like dependency graphs [19], $\tilde{O}\left({\log }^{4}n\right)$ for deterministic algorithms in general graphs [22, 29, 27], and $O\left(\frac{d}{\log d}\right)+\tilde{O}({\log }^4\log n)$ for randomized algorithms in general graphs [22, 29, 27, 23].

In the following, we describe each step of the algorithm separately.

We first select a subgraph $G^{\prime }=(V^{\prime },E^{\prime })$ of $G$ on which we solve the problem. The node set of $G^{\prime }$ is $V^{\prime }=V$ and to construct the edges $E^{\prime }$, each $v\in V$ with $d_G(v)\ge 3$ arbitrarily marks $3$ of its edges. If an edge $e=\{u,v\}$ is marked by both $u$ and $v$, it is included in $E^{\prime }$. Since an edge is added to $E^{\prime }$ only if both of its endpoints have marked it and each node marks at most $3$ edges, the maximum degree of $G^{\prime }$ is $\le 3$.

Given a valid red-blue coloring of the half-edges of $G^{\prime }$ ⁶⁶6A valid red-blue coloring is a red-blue assignment on the half-edges of a graph that aligns with the edge types and satisfies the vertex constraints of the graph., we can construct a valid red-blue coloring on $G$ as follows. Nodes of degree $3$ in $G^{\prime }$ already have at least one incident half-edge of each color. All other nodes $v$ of degree at least $3$ in $G$ have $3-d_{G^{\prime }}(v)$ marked edges that are not in $G^{\prime }$. Those edges are not marked by their other node and $v$ can therefore color them arbitrarily. If there are at least two such edges, $v$ colors them such that the two corresponding incident half-edges get different colors. If it has only one such edge, it already has incident half-edges of at least one color and it can color the remaining marked edge with the other color. The conversion from $G$ to $G^{\prime }$ and computing a solution on $G$ when given a solution on $G^{\prime }$ both clearly require only $O(1)$ rounds. Given a valid red-blue for $G^{\prime }$, we can derive a valid red-blue coloring for the original graph $G$. Therefore, in the following, we describe how to create a valid red-blue coloring for $G^{\prime }$.

Next, we compute a $(3,2)$-ruling set $S$ on $G^{\prime }$. That is, we select a set of nodes $S$ such that for any two nodes $u,v\in S$, the distance between $u$ and $v$ in $G^{\prime }$ is at least $3$ and for any node $u\notin S$, there is a node in $S$ within distance $2$ in $G^{\prime }$. Such a set $S$ can be computed in $O({\log }^{\ast }n)$ rounds by running an MIS algorithm on $G^{\prime 2}$ [40]. Note that $G^{\prime 2}$ is a bounded-degree graph and the $\mathrm{𝖫𝖮𝖢𝖠𝖫}$ model on $G^{\prime 2}$ can be simulated with constant overhead in the $\mathrm{𝖫𝖮𝖢𝖠𝖫}$ model on $G$. Given $S$, we partition $G^{\prime }$ into clusters. We build one cluster for each node $v\in S$, where each node $u\notin S$ joins the cluster of the nearest $S$-node (ties broken arbitrarily). Note that since nodes in $S$ have distance at least $3$ from each other, each cluster consists at least its cluster center $v\in S$ and all neighbors $u$ of $v$ in $G^{\prime }$. Further, since every node is at distance at most $2$ from a cluster center, the cluster of $v\in S$ is contained within $v$’s $2$-hop neighborhood.

Clusters are called good if they include a vertex with degree less than $3$ or if they contain a cycle, and bad otherwise. Note that the subgraph induced by the nodes of a bad cluster is a tree of height at most $2$ (when rooted at the cluster center $v\in S$). Since any bad cluster centered at $v\in S$ contains at least the three neighbors of $v$, each bad cluster has at least six intercluster edges, where an intercluster edge is an edge that connects endpoints in two distinct clusters. In the following, we first color the internal edges of the bad clusters and the intercluster edges, and we afterwards color the internal edges of good clusters.

Before coloring any edges, we assign each intercluster edge to one of its two incident clusters. To this end, we construct a multigraph $H=(V_H,E_H)$ as follows. The graph $H$ contains one node $v_C\in V_H$ for each good cluster $C$ of $G^{\prime }$ and two nodes $v_{C,1}$ and $v_{C,2}$ for each bad cluster $C$ of $G^{\prime }$. Further, the edge set $E_H$ contains one edge for each intercluster edge of $G^{\prime }$. An intercluster edge $\{u,v\}\in E^{\prime }$ is assigned to an edge in $E_H$ as follows. The edge is between two cluster nodes in $V_H$ corresponding to the clusters containing $u$ and $v$. For each bad cluster $C$, we make sure that both nodes $v_{C,1}$ and $v_{C,2}$ obtain at least $3$ edges. Note that this is possible because each bad cluster is incident to at least $6$ intercluster edges. We then apply the sinkless orientation algorithm on this modified graph, which requires ${𝖳}_{\mathrm{𝖲𝖮}}$ time. As a result, any node of $H$ of degree at least $3$ is ensured to have at least one outgoing edge. We assign each edge in $E_H$ to the node in $V_H$ for which it is outgoing. This directly induces an assignment of the intercluster edges of $G^{\prime }$ to one of the adjacent clusters. Note that because each bad cluster has two nodes of degree $\ge 3$ in $H$, each bad cluster is assigned at least two of its intercluster edges.

We can now assign the colors to all edges inside the bad clusters and to all intercluster edges. Recall that each bad cluster has at least two adjacent intercluster edges that are assigned to it. We arbitrarily name one of those edges $e_c$ and another one of those edges $e_{nc}$. We color the half-edges of all the intercluster edges that are assigned to a good cluster and the half-edges of all the intercluster edges that are assigned to a bad cluster and that are not selected as the edge $e_{nc}$ of this cluster. This coloring is done so that it is consistent with the types of the colored edges, but otherwise it is done arbitrarily. In each bad cluster, we now identify the (unique) path between $e_{nc}$ and $e_c$. We assume that the path includes $e_{nc}$, but it excludes $e_c$, Figure 1 (a). We now $2$-color the half-edges on this path, starting from the edge incident to the endpoint of $e_c$ and moving towards $e_{nc}$, in accordance with the edge types in such a way that each inner node of the path has one adjacent red and one adjacent blue half-edge on the path. Because the cluster diameter is bounded, the path length is constant and thus, the $2$-coloring of the path can be done in $O(1)$ rounds. Assume that all the remaining edges inside the cluster are oriented towards the $e_c\text{-}{e}_{nc}$-path, Figure 1 (b). Those edges are now colored by going from the leaves of the internal cluster tree towards the $e_c\text{-}{e}_{nc}$-path. Consider such a remaining edge $\{u,v\}$ inside the cluster and assume that $v$ is the parent of $u$ (i.e., $v$ is the node closer to the $e_c\text{-}{e}_{nc}$-path). When coloring the edge $\{u,v\}$, node $u$ already has two colored half-edges. We can therefore color the edge $\{u,v\}$ so that node $v$ is happy, i.e., has two incident half-edges of different colors, Figure 1 (c). In this way, we can make all nodes happy except the nodes on the path. However, we have already made sure that the path nodes see both colors on their two edges on the path. In this way, we can therefore make all the nodes in the bad clusters happy.

We can move on to the good clusters. Note that at this point, all the intercluster edges are colored and it therefore only remains to color the internal edges of all the good clusters. Let us first assume that we have a good cluster that contains at least one node of degree at most $2$ and let $v_2$ be such a node. Node $v_2$ has a degree less than $3$ and nodes of degree less than $3$ do not have to satisfy any constraints. Therefore, all the edges incident to $v_2$ can be colored freely (from $v_2$’s point of view). We now construct a spanning tree $T$ of the internal edges of the cluster and we orient the edges of $T$ towards $v_2$. We arbitrarily color all edges in the cluster that do not belong to $T$. We then proceed to $2$-color the half-edges of $T$ starting from the leaves, moving towards $v_2$. Going up the oriented tree $T$, we can make each node happy except for the root of $T$, which is happy by default because its degree is less than $3$. This process is also completed within $O(1)$ rounds.

We next turn our attention to good clusters that contain only nodes of degree $3$, but include a cycle. If a cluster contains only one cycle, we select it. If there are multiple cycles, we select an arbitrary one, Figure 2 (a). Subsequently, we contract the selected cycle into a single vertex $v$ and we construct a spanning tree $T$ of the remaining graph in the cluster. We arbitrarily color all edges in the cluster that do not belong to $T$ or the selected cycle. The tree edges are colored in the same way as before, Figure 2 (b). However, this time, the root node corresponds to the nodes of a cycle in $G^{\prime }$ and thus, the root is not automatically happy. However, since each node on the cycle has degree $3$ and exactly two incident edges within the cycle, after coloring all the edges except for the cycle edges, each node of the cycle already has one colored incident edge. To color the edges of the cycle, we consistently orient the cycle in one of the two directions. Now, each node $v$ in the cycle is responsible for coloring its outgoing edge and it colors it to make itself happy, Figure 2 (c). This concludes the algorithm. Note that also the good clusters can clearly be processed in $O(1)$ rounds.

The most time-consuming part of the whole algorithm is the computation of the sinkless orientation of the cluster graph $H$. All other steps require either $O(1)$ or $O({\log }^{\ast }n)$ rounds. The overall round complexity is therefore ${𝖳}_{\mathrm{𝖲𝖮}}$. $◀$

We can now prove the first part of Theorem 1.

The high-level idea of the proof is the following. For $k=\lceil {\log }_2\mathrm{\Delta }\rceil$, we compute a sequence of multigraphs $G=G_0,G_1,G_2,\mathrm{\dots },G_{k+2}$ of maximum degree $\mathrm{\Delta }={\mathrm{\Delta }}_0,{\mathrm{\Delta }}_1,\mathrm{\dots },{\mathrm{\Delta }}_{k+2}$ such that the maximum degree ${\mathrm{\Delta }}_{i+1}$ of $G_{i+1}$ is roughly ${\mathrm{\Delta }}_{i+1}\approx {\mathrm{\Delta }}_i/2$ and such that ${\mathrm{\Delta }}_{k+2}\le 4$. The graphs are constructed such that solving the problem required by Equation 3 on any graph $G_i$ solves the same problem on $G$. The full proof of the lemma appears in the full version on Arxiv [15]. $◀$

Section 3 already proves the first part (Equation 1) Theorem 1. The next lemma shows how to also prove the second part (Equation 2) of the theorem.

Note that for odd-degree nodes, the condition of Equation 4 is implied by the condition of Section 3. Our approach therefore is to reduce the problem on general graphs to the problem on graphs with only odd-degree nodes and to then use Section 3. For this, we use the fact that all edges of $G$ are of type $𝖢$ (i.e., we need to compute a red/blue-coloring of the edges of $G$). The reduction consists of two steps.

Let $V_E\subseteq V$ be the set of nodes that have an even degree in $G$ and let $G[V_E]$ be the subgraph of $G$ induced by $V_E$. As the first step, we compute a maximal matching $ℳ$ of $G[V_E]$. This can be done in $O(\mathrm{\Delta }+{\log }^{\ast }n)$ rounds (e.g., [40]). In the end, the edges of $ℳ$ will be labeled $𝖱$ (i.e., both their half-edges are labeled $𝖱$). We now however first remove the edges of $ℳ$ from the graph. Let $V_M\subseteq V_E$ be the set of nodes that are incident to an edge in the matching $ℳ$, let $E^{\prime }:=E\setminus ℳ$, and let $G^{\prime }=(V,E^{\prime })$. Note that in graph $G^{\prime }$, all nodes in $V_M$ now have an odd degree (because they lost exactly one of their edges) and the only nodes of even degree are the nodes $V_E^{\prime }:=V_E\setminus V_M$. Because of the maximality of $ℳ$, the nodes in $V_E^{\prime }$ form an independent set of $G^{\prime }$. Therefore, the nodes in $V_E^{\prime }$ can pair up their edges and create a virtual edge of type $𝖮$ out of each of those pairs. Assume that $v\in V_E^{\prime }$ and that we pair up two edges $\{v,u\}$ and $\{v,w\}$ to create the virtual edge $\{u,w\}$ of type $𝖮$. The half-edges of $\{u,w\}$ correspond to the edges $\{v,u\}$ and $\{v,w\}$ and when computing a valid assignment of labels to $\{u,w\}$, we therefore color one of the two edges of $v$ red and the other one blue. Node $v$ therefore gets exactly the same number of red and blue edges and it therefore clearly satisfies the requirement of Equation 4.

The next graph $G^{\prime \prime }=(V^{\prime \prime },E^{\prime \prime })$ is now built as follows. The set of nodes of $G^{\prime \prime }$ is $V^{\prime \prime }=V\setminus V_E^{\prime }=(V\setminus V_E)\cup V_M$ and the set of edges consists of all edges of $E^{\prime }$ that are not incident to some node in $V_E^{\prime }$ and it consists of the virtual edges that are created when removing the nodes in $V_E^{\prime }$. Note that $G^{\prime \prime }$ can be a multigraph even if $G$ and $G^{\prime }$ are simple graphs. Note also that $G^{\prime \prime }$ has only odd-degree nodes. All nodes that have an odd degree in $G$, i.e., the nodes $V\setminus V_E$ have the same degree in $G^{\prime \prime }$. All nodes in $V_M$ have their original (even) degree minus $1$ (from removing $ℳ$).

In order to compute the labeling of $G$, we now apply Section 3 to graph $G^{\prime \prime }$ (note that one $\mathrm{𝖫𝖮𝖢𝖠𝖫}$ round in $G^{\prime \prime }$ can be simulated in $2$ $\mathrm{𝖫𝖮𝖢𝖠𝖫}$ rounds in $G$). Let $v\in V^{\prime \prime }$ be a node of $G^{\prime \prime }$ and let $d^{\prime \prime }(v)$ be the (odd) degree of $v$ in $G^{\prime \prime }$. Section 3 implies that the red and blue degree of $v$ in $G^{\prime \prime }$ are either $\lfloor d^{\prime \prime }(v)/2\rfloor$ or $\lceil d^{\prime \prime }(v)/2\rceil =\lfloor d^{\prime \prime }(v)/2\rfloor +1$. For the nodes $v\in V\setminus V_E$, we have $d(v)=d^{\prime \prime }(v)$ and thus also $d_{𝖱}(v),d_{𝖡}(v)\in \{\lfloor d(v)/2\rfloor ,\lfloor d(v)/2\rfloor +1\}$ as required by Equation 4. For $v\in V_M$, we have $d(v)=d^{\prime \prime }(v)+1$ and since the edges of $ℳ$ are colored red, we have $d_{𝖱}(v)\in \{\lfloor d^{\prime \prime }(v)/2\rfloor +1,\lfloor d^{\prime \prime }(v)/2\rfloor +2\}=\{\lfloor d(v)/2\rfloor ,\lfloor d(v)/2\rfloor +1\}$. This completes the proof. $◀$

Note that by switching the names of the colors, the algorithm of Section 3 can also be used to guarantee the following condition.

We first describe the transformation from $\mathrm{\Pi }(2y)$ to $\mathrm{\Pi }(y)$.

If $y\le \frac{\mathrm{\Delta }-2}{2}$, let $E^{\prime }$ be the set of red edges in the given solution to $\mathrm{\Pi }(2y)$ and let $G^{\prime }$ be the subgraph of $G$ induced by $E^{\prime }$. We apply Section 3 (with Equation 4) to $G^{\prime }$. The edges that are colored red in the resulting red-blue labeling of $G^{\prime }$ remain red and the remaining edges of $E^{\prime }$ together with the edges in $E\setminus E^{\prime }$ become blue in the final labeling.

If $y>\frac{\mathrm{\Delta }-2}{2}$, we first switch the colors in the given solution to $\mathrm{\Pi }(2y)$. Let $E^{\prime }$ be the set of red edges in the current solution to $\mathrm{\Pi }(2y)$ and let $G^{\prime }$ be the subgraph of $G$ induced by $E^{\prime }$. We apply Section 3 (with Equation 4) to $G^{\prime }$. The red edges in the resulting red-blue labeling of $G^{\prime }$ remain red and the remaining edges of $E^{\prime }$ together with the edges in $E\setminus E^{\prime }$ become blue. We then again switch the colors for the final labeling of the edges.

For the analysis, again first consider the case $y\le \frac{\mathrm{\Delta }-2}{2}$. For a node $v$, let $d_{𝖱}^{\prime }(v)$ be its degree in $G^{\prime }$ (i.e., $d_{𝖱}^{\prime }(v)$ is the number of red edges in the initial solution to $\mathrm{\Pi }(2y)$). We further use $d_{𝖱}(v)$ to denote the number of red edges after executing the algorithm. We thus need to show that the values of $d_{𝖱}(v)$ satisfy the requirements of problem $\mathrm{\Pi }(y)$. Note that for every $v\in V$, by Equation 4, the number of red edges after executing the algorithm is

We first concentrate on nodes $v$ that have degree $\mathrm{\Delta }$ in $G$. Since the initial red-blue labeling is a solution to $\mathrm{\Pi }(2y)$, we know that for each such node $v$, $d_{𝖱}^{\prime }(v)\in \{2y,2y+1\}$. Note that $\lfloor (2y)/2\rfloor =\lfloor (2y+1)/2\rfloor =y$. We therefore have $d_{𝖱}(v)\in \{y,y+1\}$ as it is required for nodes of degree $\mathrm{\Delta }$ in problem ${\mathrm{\Pi }}_{\mathrm{\Delta }}(y)$ (and thus in problem $\mathrm{\Pi }(y)$). The extension to the conditions for is deferred to the full proof in [15]. For the case $y>\frac{\mathrm{\Delta }-2}{2}$, we use Section 4 to switch to the equivalent problem $\mathrm{\Pi }(\mathrm{\Delta }-1-y)$. For this problem, we can then apply the analysis of the first case. The details appear in the full proof in [15]. $◀$

We next show that a solution to $\mathrm{\Pi }(2y+1)$ or to $\mathrm{\Pi }(2y-1)$ (depending on the value of $y$) can be also used to compute a solution to $\mathrm{\Pi }(y)$. The algorithm and also its proof are similar to the case of Section 4. The proof is provided in [15].

We are now ready to prove Theorem 4, i.e., that for every $y\in \{0,\mathrm{\dots },\mathrm{\Delta }-2\}$, problem $\mathrm{\Pi }(y)$ can be computed in time $O(\log \mathrm{\Delta })\cdot {𝖳}_{\mathrm{𝖡𝖮}}(\mathrm{\Delta })$.

We first note that for some values of $y$, $\mathrm{\Pi }(y)$ is straightforward to obtain. First, $\mathrm{\Pi }(0)$ can be solved in $0$ rounds by just coloring all edges blue. In this scenario, ${\mathrm{\Pi }}_{\mathrm{\Delta }}(0)$ is satisfied and for all vertices with degree , leads to $x_d=0$, thereby satisfying $\mathrm{\Pi }(0)$. Further, by using Section 3 (i.e., the second part claim of Theorem 1), we can compute a red-blue coloring of the edges that satisfies Equation 4 (or one that satisfies Equation 5). This approach directly satisfies ${\mathrm{\Pi }}_{\mathrm{\Delta }}(y)$ for $y=\lfloor \frac{\mathrm{\Delta }}{2}\rfloor$. For vertices of degree , the value of ${\tilde{x}}_d$ is determined as follows, based on whether $\mathrm{\Delta }$ is odd or even:

• $\mathrm{■}$

  For even $\mathrm{\Delta }$: ${\tilde{x}}_d=\frac{d}{\mathrm{\Delta }}\left(\frac{\mathrm{\Delta }}{2}+\frac{1}{2}\right)=\frac{d}{2}+\frac{d}{2\mathrm{\Delta }}$. If $d$ is odd, then $x_d=\frac{d-1}{2}$ (), and the values $\lfloor \frac{d}{2}\rfloor$ and $\lfloor \frac{d}{2}\rfloor +1$ fall within the set $\{\frac{d-3}{2},\frac{d-1}{2},\frac{d+1}{2}\}$. For even $d$, $x_d=\frac{d}{2}$, with $\lfloor \frac{d}{2}\rfloor$ and $\lfloor \frac{d}{2}\rfloor +1$ belonging to the set $\{\frac{d}{2}-1,\frac{d}{2},\frac{d}{2}+1\}$.

• $\mathrm{■}$

  For odd $\mathrm{\Delta }$: ${\tilde{x}}_d=\frac{d}{\mathrm{\Delta }}\cdot \frac{\mathrm{\Delta }}{2}=\frac{d}{2}$. If $d$ is odd, then $x_d=\frac{d-1}{2}$ and if $d$ is even $d$, $x_d=\frac{d}{2}$, which are the two cases that were already covered in the previous case.