arXiv:1711.05469v1 [cs.DS] 15 Nov 2017

Deterministic Distributed Edge-Coloring
with Fewer Colors
Mohsen Ghaffari · ETH Zurich · ghaffari@inf.ethz.ch

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

Yannic Maus1 · University of Freiburg · yannic.maus@cs.uni-freiburg.de

Jara Uitto1 · ETH Zurich and University of Freiburg · jara.uitto@inf.ethz.ch

Abstract
We present a deterministic distributed algorithm, in the LOCAL model, that computes a (1 + o(1))∆edge-coloring in polylogarithmic-time, so long as the maximum degree ∆ = Ω̃(log n). For smaller ∆,
we give a polylogarithmic-time 3∆/2-edge-coloring. These are the first deterministic algorithms to go
below the natural barrier of 2∆ − 1 colors, and they improve significantly on the recent polylogarithmictime (2∆−1)(1+o(1))-edge-coloring of Ghaffari and Su [SODA’17] and the (2∆−1)-edge-coloring of
Fischer, Ghaffari, and Kuhn [FOCS’17], positively answering the main open question of the latter. The
key technical ingredient of our algorithm is a simple and novel gradual packing of judiciously chosen
near-maximum matchings, each of which becomes one of the color classes.

1

Supported by ERC Grant No. 336495 (ACDC).

1 Introduction & Related Work
Edge-coloring is one of the four classic problems in the subarea of local distributed algorithms—along
with vertex-coloring, maximal independent set (MIS), and maximal matching—which have been studied
extensively since the 1980s; see, e.g., the distributed graph coloring book of Barenboim and Elkin [BE13].
While there are rather satisfactory randomized algorithms, finding efficient deterministic algorithms consitute some of the most well-known and central open questions of the area; see, e.g., the first five open
problems of [BE13]. In this paper, we present efficient deterministic edge-coloring algorithms that use considerably fewer colors, for the first time going below the barrier of 2∆ − 1 colors, where ∆ denotes the
maximum degree.

1.1 Background
LOCAL Model. We work with the standard LOCAL model of distributed computing, usually attributed
to Linial [Lin92]: the network is abstracted as an n-node undirected graph G = (V, E), and each node
is labeled with a unique O(log n)-bit identifier. Communication happens in synchronous message passing
rounds, where in each round each node can send a message to each of its neighbors. At the end of the
algorithm, each node should output its own part of the solution, e.g., the colors of its incident edges in the
edge-coloring problem. The time complexity of an algorithm is the number of synchronous rounds.
History, The Journey to Deterministic (2∆ − 1)-Edge-Coloring: Any graph with maximum degree
at most ∆ admits a (2∆ − 1)-edge-coloring, by a trivial sequential greedy algorithm. Moreover, a very
simple randomized distributed algorithm, following from Luby’s 1986 MIS algorithm [Lub86, ABI86], can
compute such a coloring in O(log n) rounds. This made computing a (2∆ − 1)-edge-coloring a natural firsttarget for deterministic distributed algorithms. However, in contrast to randomized algorithms, computing
such a coloring deterministically and efficiently (in polylogarithmic time) remained an open problem for
about 30 years (see, e.g., Open Problem 11.4 in the distributed graph coloring
book [BE13]). Until very
√
recently, the best known round complexity for (2∆ − 1)-edge-coloring was 2O( log n) by using an algorithm
of [PS95b].
A brief recap of the concrete steps of progress is as follows: Since Linial’s pioneering 1987 paper [Lin92]
and for many years, O(∆2 )-colors was the best known palette size for polylogarithmic-time algorithms.
Two intermediate steps of progress were polylogarithmic-time algorithms of Czygrinow et al. [CHK01] for
O(∆ log n)-edge-coloring and that of Barenboim and Elkin [BE11] for ∆ · 2O(log ∆/ log log ∆) -edge-coloring.
More recently, a significant leap was made by Ghaffari and Su [GS17] who presented a (2 + o(1))∆-edgecoloring in polylogarithmic-time. Finally, the question was settled very recently when Fischer, Ghaffari
and Kuhn [FGK17] presented a O(log7 ∆ log n)-round deterministic distributed algorithm for (2∆ − 1)edge-coloring. For ((2 + o(1))∆)-edge-coloring, a simpler and faster algorithm with time complexity
Õ log2 ∆ · log n) was given recently by Ghaffari et al. [GHK+ 17b].2
In the special case where ∆ is assumed to be small and we investigate the complexity’s dependency on
∆, the following results were presented for (2∆ − 1)-edge-coloring: Panconesi and Rizzi [PR01] gave an
O(∆ + log∗ n)-round algorithm. This was improved by Barenboim [Bar15] to O(∆3/4 log ∆ + log∗ n) and
then further to O(∆1/2 log5/2 ∆ + log∗ n) by Fraigniaud, Heinrich and Kosowski [FHK16]. The last two
results solve the more general problem of (∆ + 1)-vertex coloring problem.
Going Below 2∆ − 1 Colors: By a classic result of Vizing [Viz64, Bol98], any graph admits a (∆ + 1)edge-coloring. However, the proofs of existence and the algorithms for computing such a coloring are
fundamentally different from those for (2∆ − 1)-edge-coloring: for instance, for (2∆ − 1) coloring, any
partial coloring can be extended to a full coloring of all edges, without altering the already colored edges;
2

˜ to hide factors that are polynomial in O(log log n).
Throughout the paper, we use O(·)

1

moreover, this is the smallest number of colors for which such an extension is always possible. Furthermore,
all known proofs of (∆ + 1)-edge-coloring rely on very non-local arguments, in the sense that coloring one
more edge may depend on the color of (and may end up recoloring) edges that are even Θ(n)-hops away.
Similarly, (2∆ − 1) colors have been viewed as a natural barrier for deterministic edge-coloring algorithms and no such algorithm was known that uses (considerably) less than 2∆ − 1 (formally less than
2∆ − 2 colors), even for low-degree graphs. This remained a known open question since the 1990’s,
see e.g., Panconesi and Srinivasan [PS92]. Note that in contrast, at least for low-degree graphs—e.g.,
when ∆ ≤ poly log(n)—computing a (2∆ − 1)-edge-coloring is easy, and was known since Linial’s paper [Lin92].
Given that the (2∆−1)-edge-coloring problem is solved, and noting this intrinsic change in the nature of
the problem once we go below 2∆ − 1 colors, an intriguing question that remained open, and was explicitly
asked by Fischer et al. [FGK17], is
“How close can we get to this [Vizing’s edge-coloring], while remaining in polylogarithmic-time?”

1.2 Our Contributions
In this paper, we almost settle the above question. Concretely, we get a deterministic distributed coloring
that is within a 1 + o(1) factor of Vizing’s bound, so long as ∆ = ω(log n), and for smaller degrees, we
show how to get 3∆/2-edge-coloring. Below, we present the formal statement of the results—the precise
constants in the exponents are not optimized and can be found in the technical section.
Theorem 1.1. There is a constant c > 0 such that for every ε > 0 there exist deterministic distributed
algorithms that color the edges of any n-node graph that has maximum degree at most ∆ with

• ∆ + ε∆ colors if ∆ ≥ c · ε−1 · log ε−1 · log n in O ε−9 logO(1) n rounds

• 3∆/2 colors for all ∆ in O ∆9 logO(1) n rounds.

We remark that the complexities stated above depend in a black-box manner on the complexity of
computing hypergraph maximal matchings and (1 − ε)-approximations of weighted maximum matching.
Above, we have stated the bound based on the current state of the art, which are presented in the concurrent work [GHK17a]; our technical sections make this dependency explicit. If one prefers not to depend
on this simultaneous work [GHK17a], we could use the solutions provided in [FGK17], and still obtain a
polylogarithmic-time (1 + ε)∆-edge coloring for arbitrarily small constant ε > 0.
Another remark is that one can choose the ε parameter in Theorem 1.1 to be quite small, and as a result,
can get a coloring with ∆ + poly(log n) colors, as we formalize in the next√corollary. This is interesting
because the known randomized methods cannot go below the bound of ∆ + ∆ colors, which is a natural
barrier for those methods [CHL+ 18], rooted in the standard deviations of the random nibble step.
Corollary 1.2. There is a deterministic distributed
algorithm
that


 colors the edges
 of any n-node
 graph with
O(1)
∆
9
maximum degree at most ∆ with ∆ + O log n log 2 + log n
colors in O ∆ + log
n rounds.

Finally, we note that in a recent simultaneous work, Ghaffari, Harris, and Kuhn [GHK17a] present a
generic method for derandomizing local distributed algorithms. As we explain in Section 5, combining
their result with the randomized edge coloring algorithm of [CHL+ 18], we can obtain an alternative method
for proving a slightly weaker version of the first part of Theorem 1.1. We still believe that the algorithm
that we present in the main body of this paper has a number of advantages: (1) the lower bound on ∆ for
which this method works is better, (2) it is much simpler, cleaner, and more comprehensible in comparison
with the algorithm that comes out of the “automated” application of derandomization (via a certain method
of conditional expectations) atop the non-trivially complex randomized algorithm of [CHL+ 18], (3) the
computations and communications in this main algorithm are simpler and more efficient, e.g., the algorithm
fits in the CONGEST model, modulo the part of (1 − ε)-approximation of maximum-weight matchings,
which itself can presumably be improved in the future to work in the CONGEST model.
2

1.3 Our Method in a Nutshell
Here, we provide a brief outline of our (1 + o(1))∆-edge-coloring algorithm, which is made of two components. The latter of which is the main novelty of this paper. The first component is a splitting algorithm,
borrowed from [GS17, GHK+ 17b], which partitions the edge-set of the graph into roughly (1 + o(1))∆/d
disjoint sets, each of which forms a spanning subgraph with max-degree d = Õ(log n). This effectively
means that all that remains to be solved is (1 + o(1))∆-edge-coloring for graphs of maximum degree
Õ(log n).
We now discuss our (1 + o(1))∆-edge-coloring for low-degree graphs, which is our main technical
contribution. This algorithm is based on an iterative packing of judiciously crafted matchings, each of
which will be one color class. To provide some intuition for this, let us consider a simple (though not ideal)
algorithm for the easier objective of (2∆ − 1)-edge-coloring: simply, for 2∆ − 1 iterations, in each iteration
i, compute a maximal matching, color all of its edges with color i, and remove them from the graph. This
will color all the edges because in each iteration, for each remaining edge e, either edge e or at least one
of its incident edges gets colored. To get to a (1 + o(1))∆-edge-coloring, our hope is that the matching
computed in each iteration is more “expansive” and for each remaining edge e (formally, some appropriate
relaxation of this “for each” guarantee), the computed matching removes at least two of its incident edges.
This way, the neighborhood of e drops at a rate of two edges per iteration and thus, the 2∆ − 1 edges in this
neighborhood are expeced to get exhausted in about ∆ iterations, i.e., after about ∆ colors.
To gain more intuition, let us consider another hypothetical scenario, a bipartite ∆-regular graph. This
graph has a perfect matching [Alo03, Viz64]; if we could compute such a matching distributedly, we could
remove it, remain with a bipartite (∆ − 1)-regular graph, and repeat, eventually ending with a ∆-edgecoloring. However, we cannot compute a perfect matching efficiently in the distributed setting (this problem
may need Ω(n) rounds). Our hope would be to use instead some near-maximum matching, but this creates
some irregularity in the degrees, which can grow as we continue adding more and more matchings. Our
algorithm follows a similar outline but has to be much more careful in managing these irregularities.
Concretely, the algorithm’s core is as follows: For simplicity, assume that ∆ is lower bounded by some
sufficiently large polylogarithmic bound; the actual algorithm which optimizes this lower bound will need
more care. For some T = Θ(log n) iterations, in each iteration t ∈ {1, 2, . . . , T }, we find a near-maximum
matching with the following special property: For each i ∈ {1, . . . , t}, for the set Si of all nodes of degree
at least ∆ − i, this single matching is incident on a (1 − o(1))-fraction of Si . We call such a structure a
pervasive matching. One can see that for each i, such a matching exists. The core technical challenge in our
algorithm will be to find one matching that satisfies this property for all i simultaneously. Our algorithm for
computing a pervasive matching is abstracted by Lemma 2.1 and its proof appears in Section 2.1. After T
steps, as we will show, this will ensure that the maximum degree has reduced by about T (1 − o(1)). Hence,
repeating this idea will result in a (1 + o(1))∆-edge-coloring, in roughly (1 + o(1))∆ iterations. Once the
remaining degree ∆′ becomes too small, say ∆′ = o(∆), we cannot find such a nice matching, but we clean
up that case more coarsely, by just packing maximal matchings; we thus use about 2∆′ colors at that point,
but this 2-factor is negligible overall and we still get a (1 + o(1))∆-edge-coloring.
Our 3∆/2-edge-coloring algorithm also has a similar iterative structure, but now each iteration extracts
some special subgraph, called (3)-graph, instead of a matching. This structure is such that (1) we are able to
color its edges using 3 colors, and (2) removing it reduces the maximum degree upper bound by an additive
2. The extraction of (3)-graphs itself relies on the computation of a sequence of five maximal and maximum
matchings of subgraphs of G; the latter is possible locally only thanks to the extra special properties of the
bipartite graphs in consideration in those intermediate steps of the algorithm.

1.4 Other Related Work
Randomized Edge-Coloring Algorithms: The classic randomized MIS algorithm of Luby [Lub86,ABI86]
leads to a randomized (2∆ − 1)-edge-coloring algorithm with runtime O(log n). This was improved to
3

√
√
√
O(log ∆ + 2 log log n ) by Barenboim et al. [BEPS12] and to O( log ∆ + 2 log log n ) by Harris, Schneider
and Su [HSS16], both of which work also for the more general problem of (∆ + 1)-vertex-coloring. Fischer
et al. [FGK17] gave a randomized (2∆ − 1)-edge-coloring algorithm with complexity O(log8 log n).
In contrast to the deterministic setting there are quite a few randomized algorithms which use fewer
than 2∆ − 1 colors. The first such result was by Panconesi and Srinivasan [PS92]; their result was later
improved Dubhashi, Grable, Panconesi, to a (1 + ε)∆-edge-coloring algorithm in polylogarithmic time with
the restriction that ∆ = Ω(log1+Ω(1) n). The time complexity
for the same number of colors was improved
n 
,
[EPS15].
In [CHL+ 18] Chang, He, Li, Pettie, and
Elkin, Pettie und Su to O log∗ ∆ · max 1, ∆log
1−o(1)
√
Uitto recently showed how to edge-color a graph with ∆+ Õ( ∆) colors in O(log ∆·TLLL ) where TLLL is
the complexity of a permissive version of the constructive Lovász local lemma. We also refer to [CHL+ 18]
for a more detailed survey of randomized edge-coloring algorithms.

Lower bounds for Edge-Coloring: The celebrated Ω(log∗ (n)) round complexity lower bound of Linial’s
[Lin92] still remains the only lower bound known for (2∆ − 1)-edge-coloring [Lin92]. Recently, Chang
et al. [CHL+ 18] proved that (2∆ − 2)-edge-coloring has lower bounds of Ω(log∆ n) for deterministic and
Ω(log∆ log n) for randomized algorithms. Moreover, one natural way to compute (∆ + 1)-edge-colorings
is to extend partial colorings by iteratively recoloring edges along an ‘augmenting paths’. Chang et al.
[CHL+ 18] showed that with this ‘recoloring-along-a-path’ approach one might have to recolor nodes along
paths of length Ω(∆ log n) to color a single additional edge.
Deterministic Edge-Coloring Algorithms for Low-Arboricity Graphs: In [BEM17] Barenboim, Elkin
and Maimon gave a polylogarithmic-time determinisitc (∆ + o(∆))-edge-coloring for graph with arboricity
a ≤ ∆1−ε , for a constant ε > 0. This was then improved by Fischer et al. [FGK17] to (∆ + (2 + ε)a − 1)colors. Chang et al. [CHL+ 18] present a Θ(log∆ n)-round ∆-edge-coloring algorithm for trees.
Distributed Maximum Matching Approximation: Computing almost optimal matchings is at the core
of our algorithms. The standard approach to (1 − ε)-approximate the maximum matching problem is by
Hopcroft and Karp [HK73]. The main obstacle to transfer the framework to a distributed setting is to find
maximal sets of disjoint augmenting paths of length O(1/ε). Czygrinow and Hańćkowiak gave a deterministic algorithm that runs in time logO(1/ε) n [CH03], which was recently improved to logO(log(1/ε)) n by
Fischer et al. [FGK17]. The most recent result by Ghaffari et al. [GHK17a] takes the ε-dependency out of the
exponent, yielding a poly(log n/ε)-time algorithm. On the randomized side, Lotker et al. [LPSP08] developed an O(log n/ε2 )-time (1 − ε)-approximation for maximum matching (also see [LPSP08] for additional
work on randomized distributed matching approximation).

2 Distributed Edge-Coloring Algorithm through Iterative Matchings
In this section, we first present the core of our matching algorithm which is especially efficient in graphs
with intermediate degrees—e.g., polylogarithmic—and then, in Section 2.2, we explain how to lift this
algorithm to higher degrees, with the help of splitting techniques [GS17, GHK+ 17b]. Before proceeding to
the algorithm we present some notations that we use to express our complexities.
Notation for the Complexity of Some Black-Box Subroutines Our algorithm makes use of two subroutines in a black-box manner, and thus the final complexity of our algorithm depends on the complexity of
the (best known) method for them. To express this complexity explicitly and illustrate the dependencies,
we use some notation. We define THM (n, Γ, ℓ) to be the runtime of a hypergraph maximal matching algorithm with n nodes, maximum degree at most Γ and rank at most ℓ. The best known published bound is
from [FGK17], roughly being logO(log r) ∆·log n, and an improvement to poly(r log(∆n)) was recently provided by [GHK17a]. Moreover, we define TWM (n, ∆, ε) for the runtime of a maximal (1 − ε)-approximate
weighted maximum matching on a simple graph with n nodes and maximum degree at most ∆; we provide
an upper bound on the latter in Lemma 2.5, which is at most THM (n, ∆O(1/ε) , 1/ε) · poly(log n/ε).
4

Algorithm Outline. Our edge-coloring algorithm constructs the color classes iteratively. In each iteration,
the algorithm constructs a matching that hits—i.e., is incident on— a large fraction of all the nodes. In order
to guarantee progress on all the nodes, when constructing the next matching, we make sure that the nodes
that have been hit by fewer previous matchings are given more priority to be hit by the next matching.
More precisely, in step t of the algorithm, we compute a single matching M that simultaneously hits
almost all of the nodes of degree at least ∆ − i for each i = 1, . . . , t (cf. Lemma 2.1, detailed proof in
Section 2.1). Then, we color all edges of M with an unused color and remove M from the graph. If the
initial maximum degree is large enough and we repeat this process for T = Θ(log n) steps, the maximum
degree will reduce by ≈ (1 − ε)T (cf. Lemma 2.2). Repeating this will eventually color the whole graph
with few colors. The runtime of this algorithm is inherently at least Ω(∆) as it computes the matchings
sequentially and each matching corresponds to a single color class, i.e., it is only efficient for graphs with
polylogarithmic degree. In Section 2.2 we show how degree splittings can be used to transform it into an
efficient algorithm for all degrees. The following lemma is proved in detail in Section 2.1.
Lemma 2.1. (The Pervasive Matching Lemma) Consider a graph G = (V, E) with maximum degree at
most ∆ and an integer t ≥ 0. For every ε > 0, there is an O (t/ε + TWM (n, ∆, ε/2))-round distributed
∆−i
-fraction of
algorithm to compute a maximal matching M such that for every i ≤ t, M hits a (1 − ε) · Λ+1
all the nodes of degree at least ∆ − i, where Λ ≤ ∆ exactly equals the maximum degree of G.
We continue to prove that when starting with a sufficiently large maximum degree ∆, we can reduce the
maximum degree at a rate close to one by iteratively computing matchings with Lemma 2.1. For readability,
we provide proof sketches explaining the main ideas and full proofs of the following two lemmas.
n
Lemma 2.2. Assume that we have an n-node graph G = (V, E) with maximum degree at most ∆ ≥ 2 log
ε .
 log n 
Then there is an algorithm that partially edge colors the graph with T := 4eε colors such that the
maximum degree of the uncolored graph is at most ∆ − (1 − 4eε)T .
For each of the T colors, the algorithm has round complexity O (T /ε + TWM (n, ∆, ε)) .

Algorithm: We start with all edges uncolored. In step t ∈ {1, . . . , T }, we choose the set of edges that
are to be colored with color t. Let Gt be the graph induced by the set of uncolored edges after the first
t − 1 steps and let ∆t be the maximum degree of graph Gt . With these definitions at hand, step t of the
algorithm uses a single invocation of Lemma 2.1 on Gt to compute a maximal matching M such that for
each δ ∈ {max {1, ∆ − T } , . . . , ∆}, M covers at least a (1 − ε) · ∆tδ+1 -fraction of all nodes with degree at
least δ. We assign color t to all edges in M and remove them from the graph.
We first provide a proof sketch for the Lemma to indicate the main ideas of the proof. The full proof
follows right afterwards.
Proof Sketch: The runtime of one step of the algorithm follows from the runtime of Lemma 2.1 with t = T .
In the rest of the proof we need to upper bound the maximum degree of the uncolored graph after T steps.
It is essential that the matching in a single step of the algorithm hits at least a (1 − Θ(ε))-fraction of the
large degree nodes. If we assumed a stronger requirement on ∆, e.g., ∆ ≥ 2ε−2 · log n, it is easy to see that
∆−T +1
∆−T +1
T
≥
=1−
≥ 1−ε
∆t + 1
∆+1
∆+1
holds, that is, the computed matching would hit at least a (1 − ε)2 -fraction of the nodes of degree at least
∆ − i for all i ≤ T . With the weaker assumption on ∆ one has to carefully track ∆t to (at least) show that
∆−t
for all i ≤ t we have ∆−t+i
∆t +1 ≥ ∆t +1 ≥ 1 − ε (subclaim in the full proof). Thus, the matching in step t hits
at least a (1 − ε)2 -fraction, that is, at least a (1 − 2ε)-fraction, of the nodes of degree at least ∆ − t + i for
i ≤ t. Then, by an induction on the number of rounds, one can show thatfor all i ≤ t the number of nodes
with degree at least ∆ − t + i after t steps of the algorithm is less than ti · (2ε)i · n .
5

Finally, to prove the main claim of Lemma 2.2, we need to show that the number of nodes with degree
at least ∆ − T + 4eεT + 1 after round T is smaller than one. This holds because with i = 4eεT + 1 we have
 n

 4eεT
i

 i
T = log
(i>4eεT )
4eε
2eεT
1
t
eT
(2ε)i · n =
·n
<
·n
· (2ε)i · n ≤
≤
1.
i
i
2
i
We now give a formal proof of the statement.
Proof. The runtime of one step of the algorithm follows from the runtime of Lemma 2.1 with t = T .
In the rest of the proof we upper bound the maximum degree of the uncolored graph after T steps. For
ε ≥ 1/(4e) the statement holds as ∆ − (1 − 4eε)T ≥ ∆. So from now on we assume that ε < 1/(4e).
For each t ∈ {0, . . . , T } and for all i ∈ {0, . . . , t + 1}, define K(t, i) to be the number of nodes of
degree at least ∆ − t + i after the first t steps (i.e., in graph Gt+1 ). Note that K(t, t + 1) = 0 for all t ≥ 0.
We first show by induction on t that for all t ∈ {0, . . . , T } and i ∈ {0, . . . , t}, the following holds

t
K(t, i) ≤
· (2ε)i · n.
(1)
i
Induction Base: Note that for i = 0 (and any t ≥ 0) Equation (1) is trivial as it states that K(t, i) ≤ n.
Thus, Equation (1) also holds for t = 0 because i = 0 is the only possible value with i ≤ t = 0.
Induction Step: Consider some step t ≥ 1 and i ≤ t. We first prove the following subclaim which is
necessary to show that the computed matching hits a fraction that is very close to one of the nodes of degree
at least ∆ − t + i.
Subclaim :

∆−t+i
∆t +1

≥ 1 − ε.

Proof. Let I be the smallest integer such that K(t − 1, I) = 0. By the definition of I, the maximum degree
∆t after t − 1 steps is at most ∆t ≤ ∆ − (t − 1) + I − 1 = ∆ − t + I. Then the ratio ∆−t+i
∆t +1 simplifies to
∆−t+i
∆−t+i
≥
∆t + 1
∆−t+I +1

(i≥0)

I≥0
I +1
I +1
∆−t
= 1−
.
≥ 1−
∆−t+I +1
∆−t+I +1
∆−t+1
 n
n
I+1
To show the claim we now prove that ∆−t+1
≤ ε holds. Using ∆ ≥ 2 log
and t ≤ T ≤ log
ε
4eε we can
first lower bound the denominator in the term.


log n
8e − 1
2 log n
2 log n log n
−
−
=
· log n .
(2)
∆−t+1≥
+1≥
ε
4eε
ε
4eε
4eε

≥

Next, we upper bound the nominator in the term, i.e., we upper bound I + 1. Let j ≥ log n. If j > (t − 1)
  e(t−1) j
then K(t − 1, j) = 0 by definition. Otherwise, by the induction hypothesis and using t−1
<
as
j
j

n
well as t − 1 ≤ T − 1 ≤ ⌊ log
4eε ⌋ ≤

K(t − 1, j) ≤



log n
4eε ,

we have




t−1
2εe(t − 1) j
j
·n ≤
· (2ε) · n <
j
j

n
2εe · log
4eε
j

!j

· n ≤ 1.

Thus, K(t − 1, j) = 0 holds for j ≥ log n. Hence, we obtain that I + 1 ≤ ⌈log n⌉ + 1 ≤ log n + 2.
With I + 1 ≤ log n + 2 and the lower bound on ∆ − t + 1 from Equation (2) we obtain
I +1
4e
log n + 2
≤ ε·
·
≤ ε.
∆−t+1
8e − 1
log n
The last inequality follows with n ≥ 8.


6

Now, we can proceed with proving the induction step. Recall, that t and i are fixed. Then there are two
different types of nodes of degree at least ∆ − t + i after step t: (1) Nodes of degree at least ∆ − t + i + 1
after step t − 1. (2) Nodes of degree ∆ − t + i after step t − 1 that are not hit by the matching computed in
step t. We now upper bound the number of nodes of each type.
(1) By the definition there are K(t − 1, i) nodes of type (1).
(2) We show that there are at most 2ε · K(t − 1, i − 1) nodes of type (2).

Note that ∆ − t + i lies in the range of δ when applying Lemma 2.1 as ∆ − t + i ≥ ∆ −nT . Thus, o
by
∆−t+i
Lemma 2.1, of the nodes of degree at least ∆−t+i after step t−1, at least a (1−ε)·min 1, ∆t +1 fraction is hit by the matching in step t. The subclaim
least a (1 − 2ε)-fraction.

∆−t+i
∆t +1

≥ 1 − ε implies that this fraction is at

The number of nodes that are not hit is therefore at most (1−(1−2ε))K(t−1, i−1)≤2ε·K(t−1, i−1).

Due to the bounds in (1) and (2) we obtain K(t, i) ≤ K(t − 1, i) + 2ε · K(t − 1, i − 1) and plugging
in the induction hypothesis leads to Equation (1) as follows.





t−1
t−1
t
i
i−1
K(t, i) ≤
· (2ε) · n + 2ε ·
· (2ε)
·n =
· (2ε)i · n.
i
i−1
i
This finishes the induction step.
Finally, to prove the main claim of Lemma 2.2, we show that ∆T +1 ≤ ∆ − T + 4eεT , or equivalently
that for i > 4eεT , we have K(T, i) < 1. Using Equation (1) and Ti < (eT /i)i , we get
K(T, i) <



eT
i

i

i

(2ε) · n =

The last inequality follows because T =



 log n 
4eε

2eεT
i

i

·n

(i>4eεT )

<

 4eεT
1
·n≤ 1.
2

.

Lemma 2.3. There is a constant c > 0 such that for any ε > 0 there exists deterministic distributed
algorithm that colors the edges of any n-node graph with maximum degree at most ∆≥ c · ε−1 log ε−1 log n
with ∆ + ε∆ colors and has round complexity O ∆ · (log n/ε2 + TWM (n, ∆, ε/2)) .
We first provide a proof sketch for a weaker result; the proof of the full result follows afterwards.

Proof Sketch. In the full proof of the lemma one has to apply Lemma 2.2 with increasing values for ε and
perform a careful analysis of the number of used colors. In this proof sketch we prove a slightly weaker
result, i.e., we show that we can color the graph with (1 + O(ε))∆ colors if ∆ ≥ ∆′ := 2ε−2 log n .
To obtain the desired result we apply Lemma 2.2 with ε until the current upper bound on the maximum
degree that is guaranteed by the lemma falls below ∆′ . Then perform a clean-up step in which the remaining
′
uncolored graph is colored with 2∆′ − 1 colors, e.g., by computing further
 log n2∆
 − 1 maximal matchings with
Lemma 2.1. A single application of Lemma 2.2 uses at most T = 4eε colors, reduces the maximum
∆−∆′
> 0 applications of the lemma.
degree of the graph by (1 − 4eε)T , and there are at most K = (1−4eε)T
Thus, the total number of colors is bounded by
K · T + 2∆′ − 1 ≤

∆ − ∆′
+ 2∆′ ≤ (1 + 24ε)(∆ − ∆′ ) + 2∆′ = ∆ + O(ε)∆ .
(1 − 4eε)

Computing a single color class with Lemma 2.1 needs O (T /ε + TWM (n, ∆, ε)) rounds.
 Thus, the runtime
for the (1 + O(ε))∆ color classes is bound by O ∆ · log n/ε2 + TWM (n, ∆, ε/2) .
7

We continue with the full proof.
′
i ′
Proof. Define the constant cl:= 360.
m For i = 0, . . . , l define ε := ε/120, εi := 2 ε , the threshold degrees
n
where l ≤ log 1/(4eε)′ − 1 ≤ log 1/ε + 3 is the smallest l such that
∆i := 2 log n/εi and Ti = log
4eεi
εl+1 ≥ 1/(4e) holds. Then, the algorithm consists of phases i = 0, 1, . . . , l and a clean-up step.
In phase i we apply Lemma 2.2 with εi until the current upper bound of the maximum degree, which
is guaranteed by the lemma, falls below ∆i . Then we continue to the next phase. Note that no node has
to know the actual current maximum degree of the uncolored graph for this process. After phase l the
maximum degree of the remaining graph will be at most ∆l and we use the clean-up step to color the edges
of the remaining graph with 2∆l ≤ 32e · log n ≤ 96 · log n colors, e.g., by computing 2∆l − 1 further
maximal matchings with Lemma 2.1.
We now upper bound the number of used colors. For that purpose define ∆−1 := ∆. In phase
i = 0, 1, . . . , l a single application of Lemma 2.2 reduces the maximum degree of the graph by (1 − 4eε)Ti ,
∆i−1 −∆i
we use at most Ti colors in each application of the lemma and there are at most Ki = (1−4eε
> 0
i )Ti
applications of the lemma. Thus, the total number of colors used in phase i is upper bounded by

Ki · Ti =

∆i−1 − ∆i
≤ (1 + 24εi )(∆i−1 − ∆i ) .
(1 − 4eεi )

During the l + 1 phases and the clean-up step, we use
l
l
X
X
′
24εi ∆i + ∆l
(1 + 24εi )(∆i−1 − ∆i ) + 2∆l = (1 + 24ε )∆ +
i=1

i=0

(∗)

≤ (1 + 24ε′ )∆ + (48l + 96) log n

≤ (1 + 24ε′ )∆ + (48(log 1/ε + 3) + 96) log n

≤ (1 + 24ε′ )∆ + 48 log 1/ε log n + 240 log n

(∗∗)

≤ ∆+

3
2
10
ε∆ + ε∆ + ε∆ = (1 + ε)∆ ,
15
15
15

that is, ≤ (1 + ε)∆ colors in total. At (∗) we used εi ∆i = 2 log n and ∆l ≤ 96 log n. At (∗∗) we used
24ε′ ≤ 1/5 · ε and 360 log n log ε−1 ≤ ε · ∆ .
Runtime: Computing a single color class in phase i needs
O (Ti /ε + TWM (n, ∆, εi )) = O (T /ε + TWM (n, ∆, ε))
rounds. As we compute (1 + ε)∆ color classes the total runtime is upper bounded by

O ∆ · log n/ε2 + TWM (n, ∆, ε/2) .

Lemmas 2.2 and 2.3 are simpler to prove if we tolerate a larger dependency on ǫ in the lower bound for
∆. However, with that increased dependency we would
√ not only lose in the runtime but, more importantly,
the number of colors could not go below ∆ + Ω ∆ (as in Section 2.3) regardless of the time that we
spend.

2.1 Proof of The Pervasive Matching Lemma (Lemma 2.1)
In this section we prove Lemma 2.1. First, in Section 2.1.1 we prove that a simple consequence of Vizing’s
edge coloring theorem (cf. Lemma 2.4) shows that for all i = 1, . . . there exists a maximum matching
8

∆−i
-fraction of the nodes with degree at least ∆ − i, where Λ is the exact maximum
that hits at least a Λ+1
degree of the graph. Then a distributed implementation of the CREW PRAM weighted maximum matching
approximation algorithm by Hougardy and Vinkemeier [HV06] (cf. Lemma 2.5) can be used to compute
∆−i
a matching Mi that hits a (1 − ε) Λ+1
-fraction of the nodes with degree at least ∆ − i (cf. Lemma 2.6).
∆−i
In Section 2.1.2 (Lemma 2.7) we first show how two matchings Mi and Mj where Mi hits a (1 − ε) Λ+1
∆−j
fraction of the nodes of degree at least ∆ − i and Mj hits a (1 − ε) Λ+1 -fraction of the nodes of degree at
least ∆ − j can be combined into a single matching that has both properties. Then in Lemmas 2.1 and 2.8
we compute matchings Mi for each i = 1, . . . , Θ(log n) and then use the Lemma 2.7 to iteratively combine
them into the single matching M while maintaining their properties.

2.1.1

A Matching that Hits Most Nodes of One Target Node Set

A consequence of Vizing’s edge coloring theorem [Viz64, Bol98] shows that large maximum matchings
exist. We use it to show that our maximum matching approximations hit enough nodes.
Lemma 2.4. Given a graph G = (V, E) and a node set S ⊆ V . If the maximum degree of G is Λ and all
δS
· |S| of the nodes in S.
nodes in S have degree at least δS , there exists a matching of G that hits at least Λ+1
Proof. By Vizing’s theorem, the graph G has an edge-coloring with ∆ + 1 colors. Hence, the graph G
contains ∆ + 1 disjoint matchings such that each node in S is hit by at least δS of the matchings. On
δS
average, the ∆ + 1 matchings therefore hit at least ∆+1
· |S| nodes in S. Consequently, one of the ∆ + 1
δS
matchings has to hit at least ∆+1 · |S| nodes in S.
To prove the following lemma we essentially provide a distributed version of the weighted maximum
matching approximation algorithm by Hougardy and Vinkemeier [HV06] that runs in the CREW PRAM
model. Its formal proof emphasizing the differences to the proof in [HV06] can be found in Section 4.
As combination of Lemmas 2.4 and 2.5, one obtains a distributed algorithm that finds a matching that
approximately satisfies the properties of the matching guaranteed to exist by Lemma 2.4.
Lemma 2.5. Let G = (V, E) be an n-node graph with positive edge weights w : E → R+ and let wmin
and wmax denote the minimum and the maximum edge weight, respectively. If wmax /wmin = nO(1) , then, for
every ε > 0, a maximal (1 − ε)-approximate weighted matching can be computed in time


TWM (n, ∆, ε) = O 1/ε2 + (1/ε) · THM (n, ∆O(1/ε) , 1/ε) · log n + log3 n .

Lemma 2.6. Given a graph G = (V, E) and a node set S ⊆ V . If all nodes in G have degree at most
∆ and all nodes in S have degree at least δS , then, for every ε > 0, there is a distributed algorithm with
δS
time complexity TWM (n, ∆, ε) that computes a matching that hits a (1 − ε) · Λ+1
-fraction of the nodes in S,
where Λ ≤ ∆ exactly equals the maximum degree of G.
Proof. The problem of finding a matching M of G that hits as many nodes as possible of S can be formulated
as a maximum weighted matching problem as follows. We define the weight of an edge {u, v} ∈ E of G
as w({u, v}) := |S ∩ {u, v} |. Hence, the total weight of a matching M is equal to the number of nodes in
S hit by M . Thus, Lemma 2.4 implies that a (1 − ε)-approximation of this maximum weighted matching
δS
-fraction of the nodes in S. By Lemma 2.5 such
problem gives a matching that hits at least a (1 − ε) · Λ+1
an approximate weighted matching can be computed in time TWM (n, ∆, ε). Note that when computing the
matching, edges of weight 0 can be ignored.
2.1.2

Combining Matchings while Maintaining their Properties

The core application (cf. the proof of Lemma 2.8) of the next lemma will be a combination of a matching
Ma that hits a large fraction of all nodes with a matching Mb that hits a large fraction of a subset S ⊆ V
into a single matching Mc that hits a large fraction of the nodes in S and a large fraction of all nodes.
9

Lemma 2.7. Given a graph G = (V, E) and a node set S ⊆ V . Assume that we are given two matchings
Ma and Mb of G such that matching Mb hits at least s ≤ |S| nodes of S. Then for every k ≥ 1, in O(k)
rounds, we can compute a matching Mc such that
(i) |Mc | ≥ |Ma |
(ii) V (Ma ) − (V (Mc ) ∪ S) ≤ S ∩ V (Mc ) − V (Ma ), i.e., for every node outside S that is matched by
Ma and not matched by Mcthere is a node inside S that is matched by Mc and not matched by Ma .
(iii) Mc matches at least 1 − k1 s nodes of S.

Proof. We start with some notation, then present a simple algorithm that computes the matching Mc , and
finally show that the matching has the desired properties. At first restrict Mb only to edges that have at least
one node in S. Throughout, we denote the edges in the symmetric difference of Mb and Ma as blue and
green edges, i.e., denote edges in Mb − Ma as blue edges and edges in Ma − Mb as green edges. Let Sa , Sb
and Sc denote the nodes of S that are matched by Ma , Mb and Mc , respectively.
The subgraph induced by the blue and green edges contains alternating (in blue/green) paths and cycles
as every node has at most one incident blue and green edge.
An (undirected) path p is called alternating if its edges are blue and green in an alternating manner. An
alternating path of length at least one is called a maximal alternating path if it cannot be extended to a longer
alternating path. A maximal alternating path in which at least one of its endpoint-edges is blue is called a
maximal augmenting path. Note that the graph induced by blue and green edges consists of alternating
paths and cycles and that all nodes on an alternating cycle are matched by Ma and Mb . Further note that all
maximal alternating paths are node disjoint.
Algorithm to compute Mc :
1. Add all edges of Ma to Mc .
2. For every maximal augmenting path p of length at most 4k such that at least one of its endpoints lies in
Sb − Sa remove its green edges from Mc , i.e., remove p ∩ Ma from Mc , and add its blue edges to Mc ,
i.e, add p ∩ Mb to Mc .
The algorithm is well defined and as it only imposes changes on maximal augmenting paths of length at
most 4k it can be implemented by a distributed algorithm in O(k) rounds.
Analysis: Throughout the analysis Mc and the set Sc denote the sets after the execution of the algorithm.
Matching Property: The only edges that are changed are on (short) maximal augmenting paths. For a single
maximal augmenting path, removing the green edges from the matching and adding the blue edges to the
matching does not destroy the matching property as augmenting paths are alternating and the paths are
maximal. Furthermore, all resulting maximal augmenting paths are node disjoint and thus, the operations
on all maximal augmenting paths can be performed in parallel and still result in a matching. We continue
with proving properties i) − iii).
i) As each maximal augmenting path begins with a blue edge the matching size does not decrease by
switching the edges on an augmenting path.
Here we want to emphasize that the total number of matching edges in Mc does not increase by handling
an augmenting path if the path ends with a green edge. However, the term ’augmenting path’ is still valid
in the sense that it increases the number of nodes within S that are matched.
ii) We prove this property by finding one distinct node in W1 := Sc − Sa = S ∩ V (Mc ) − V (Ma ) for
every node in W2 := V (Ma ) − (V (Mc ) ∪ S). As we add all edges from Ma to Mc in step one of the
algorithm a node v can only be in W2 if it became unmatched in step two, i.e., if v was an endpoint of a
maximal augmenting path and had an incident green edge before handling the path. However, then the
other endpoint v ′ of the path had an incident blue edge (here we use that only maximal augmenting paths
with one endpoint in Sb − Sa perform changes) and v ′ is contained in W1 . Thus, a simple induction on
the number of handled maximal augmenting paths shows the result.
iii) Every node v ∈ Sb − Sc, i.e., a node in S which is matched by Mb but is not matched by Mc at the end of
the algorithm, has an incident blue edge and no incident green edge. Thus, it lies at the start of a maximal
10

alternating path p that starts with a blue edge. As v is unmatched in Mc , the path p cannot be a maximal
augmenting path of length at most 4k. Because p starts with a blue edge this implies that the length of
p is at least 4k + 1 and p contains at least 2k nodes in Sb . As all alternating paths are node disjoint and
any path can have at most two endpoints this implies |Sb − Sc | ≤ |Sb | · 2/2k = |Sb |/k. Thus, we have
|Sc | ≥ |Sb ∩ Sc | = |Sb | − |Sb − Sc | ≥ (1 − 1/k)|Sb | ≥ (1 − 1/k)s .
The next lemma proves the main distributed matching result that is needed to iteratively compute a good
edge-coloring. For a given decreasing chain of node sets U1 ⊇ U2 ⊇ . . . Ut the lemma computes a single
matching that hits a large fraction of the nodes in each Ui , i = 1, . . . , t. In its proof we use Lemma 2.5
to compute t matchings M1 , . . . , Mt such that Mi hits a large fraction of Ui . Then we use Lemma 2.7 to
iteratively combine the matchings into a single matching while maintaining their properties.
Lemma 2.8. Let G = (V, E) be a graph with maximum degree at most ∆. Further, assume that we are
given t disjoint nodes sets V1 , V2 , . . . , Vt such that the minimum node degree of the nodes in Vi is at least δi ,
where δi ≤ δi+1 for all i ∈ {1, . . . , t − 1}.
For every ε > 0, there is a distributed O (t/ε + TWM (n, ∆, ε/2))-round algorithm that computes a
δi
maximal matching M such that for every i ∈ {1, . . . , t}, M hits an (1 − ε) · Λ+1
-fraction of the nodes in
Ui :=

t
[

Vj ,

j=i

where Λ ≤ ∆ exactly equals the maximum degree of G.

δi
-fraction of all
Proof. First, for each i ∈ {1, . . . , t} we compute a matching Mi that hits a (1 − ε/2) Λ+1
nodes in Ui by using Lemma 2.6 and the fact that all nodes in Ui have degree at least δi . All of these matchings can be computed in parallel. Now, the matching M is constructed inductively by applying Lemma 2.7 t
times. Formally, we iteratively construct matchings M1′ , . . . , Mt′ such that for each i ∈ {1, . . . , t} and each
δj
-fraction of all nodes in Uj . This proves the lemma as the
j ≤ i matching Mi′ hits at least a (1 − ε) · Λ+1
′
matching Mt satisfies all required conditions, except for the maximality. To obtain matching M we extend
Mt′ to a maximal matching in time O(log3 n) with the algorithm by Fischer [Fis17].

Inductive construction of M1′ , . . . , Mt′ : Set M1′ := M1 . For i > 1, set Mi′ := Mc where Mc is the result
′ , M = M , S = U and k = 2/ε.
of applying Lemma 2.7 with Ma = Mi−1
i
i
b
M1′ , . . . , Mt′ satisfy the required properties: The matching M1 satisfies all the properties required for
M1′ by its definition. Assume that Mj′ satisfies the required properties for j < i. We then need to show that
the matching Mc in the inductive construction of Mi′ satisfies all the properties required for matching Mi′ .
δj
′
For j < i, Mc matches at least a (1 − ε) · Λ+1
-fraction of the nodes in Uj : We already know that Mi−1
δ

j
-fraction of the nodes in Uj . This is also true for matching Mc because by
matches at least a (1 − ε) · Λ+1
′
′
Lemma 2.7, |Mc | ≥ |Mi−1 | and for every node outside Ui that is matched by Mi−1
and not matched by Mc ,
′
there is a node in Ui (and thus also in Uj ) that is matched by Mc and not by Mi−1 .
δi
δi
Mc matches a (1−ε)· Λ+1
-fraction of the nodes in Ui : As Mb = Mi matches a (1−ε/2)· Λ+1
-fraction of
δi
2
the nodes in Ui and because k = 2/ε, it follows from Lemma 2.7 that Mc matches a (1−ε/2) · Λ+1 -fraction
of the nodes in Ui . Thus, the matching Mc satisfies the required properties because (1 − ε/2)2 ≥ 1 − ε .

Runtime: As mentioned above, we first construct matchings M1 , . . . , Mt in parallel, which has runtime
TWM (n, ∆, ε/2) time. Then, we use Lemma 2.7 to inductively construct matchings M1′ , . . . , Mt′ where each
step requires O(1/ε) time. The extension to a maximal matching takes O(log3 n) = O(TWM (n, ∆, ε/2))
rounds. In total, the time complexity is O (t/ε + TWM (n, ∆, ε/2)) .
Proof of Lemma 2.1. The lemma directly follows by applying Lemma 2.8 with parameter ε and by using
the sets V1 , . . . , Vt+1 , where Vj is the set of nodes with degree ∆ − t + j − 1.
11

2.2 Polylogarithmic Runtime
The goal is to color the edges of a graph with maximum degree ∆ with (1 + ε)∆ colors while having only
polylogarithmic round complexity. As the runtime of the algorithm in Lemma 2.3 depends polynomially on
the maximum degree, it is only efficient for polylogarithmic maximum degree. We use the results on degree
splitting by Ghaffari et al. [GHK+ 17b] to transform it into an algorithm that is efficient for all degrees.
An undirected degree splitting is a partition of the edges into two sets A and B. Let E(v) denote the
edges incident to v. The discrepancy of a node v in a splitting is defined as |E(v) ∩ A − E(v) ∩ B|. The
objective in the degree splitting problem is to obtain a small discrepancy at each node, i.e., the number of
incident edges of v in the set A should be as close as possible to the number of incident edges in B.
To obtain a polylogarithmic round edge coloring algorithm we recursively split the graph until the degrees are below a threshold degree ∆′ = poly log n. Then each subgraph is colored, in parallel, with a
separate set of (1 + ε2 )∆′ colors with Lemma 2.3. This yields to an edge coloring of the original graph with
(1 + ε1 )(1 + ε2 )∆ = (1 + ε)∆ colors. The following result was shown in [GHK+ 17b].

Theorem 2.9. [GHK+ 17b] For every γ > 0, there is a deterministic Õ γ −1 · log γ −1 · log n -round
distributed algorithm for undirected degree splittings such that the discrepancy at each node v of degree
d(v) is at most γ · d(v) + 4, where Õ hides log log γ −1 factors.
Proof of Theorem 1.1. To edge-color the graph with 3/2 · ∆ colors, we use Lemma 3.5. Otherwise, we
ε1
assume that ∆ ≥ ∆′ := c · ε−1 log ε−1 · log n and we set γ = 20 log
∆ where ε1 = ε/8 and ε2 = ε/4. Then
for h recursive iterations, in each iteration, apply the splitting of Theorem 2.9 with parameter γ to each of
the parts in parallel, until we reach parts with maximum degree at most ∆′ . Here h is the largest h such that
′
′
h
( 21 + γ)h ≥ ∆
∆ which is sufficient to reduce the degree to ∆ . This way we partition G in 2 edge-disjoint
′
graphs, each with maximum degree at most ∆ . We can then, in parallel, edge-color each of these graphs
with (1 + ε2 )∆′ colors with the edge coloring algorithm from Lemma 2.3 using a separate color palette for
′
each subgraph. Now, we upper bound the number of colors. At (∗) we use ( 21 + γ)h ≥ ∆
∆ and obtain
h

2 =



1 + 2γ
1/2 + γ

h

(∗)

≤

∆
∆
(1 + 2γ)h ≤ ′ eε1 /10
∆′
∆

ε1 <1/2

≤

∆
(1 + 2ε1 ).
∆′

Thus, the total number of colors is less than 2h · (1 + ε2 )∆′ ≤ ∆ + ε∆. The round complexity of all
the splitting iterations is h · Õ γ1 · log γ1 · log n = Õ hε · log ∆ · log n which is submerged in the round
complexity of the parallel invocations of Lemma 2.3




log n
1
1
log n
′
′
O(1/ε)
3
′
+ TWM (n, ∆ , ε) = ∆ · Õ
+ 2 + · THM (n, ∆
, 1/ε) · log n + log n
∆ · Õ
ε2
ε2
ε
ε

 

log n 1
1
′
4
3
= ∆ · Õ
+ ·
log n · log n · log ∆ · log n + log n
ε2
ε
ε7


1
1
3
4
= Õ
log
n
·
log
∆
·
log
.
ε9
ε
In the above, we used that a result by Ghaffari et al. [GHK17a] that shows that

THM (n, Γ, r) = O r 2 · log(nΓ) · log n · log4 Γ .

The log log factors in γ −1 that are hidden by Õ are submerged in the final polylog runtime as the condition
on ∆ in the lemma statement shows that ǫ ≥ c/∆.

A similar for calculation for Lemma 3.5 and ∆ ≤ ∆′ leads to a runtime of Õ ∆9 log5 n log4 ∆ .

Remark. For constant ε, the runtime of Theorem 1.1 remains polylogarithmic with the upper bound on
THM (n, Γ, r) by Fischer et al. [FGK17].
12

2.3 Going Below ∆ +

√

∆ Colors

Corollary 1.2 does not have polylogarithmic runtime; however, it uses fewer colors than the known randomized methods.
Proof of Corollary 1.2. If ∆ ∈ O(log n), we can obtain a O(log n) coloring in O(∆9 · logO(1) n) =
logO(1) n rounds by Theorem 1.1. Thus, assume that∆ ∈ ω(log
 n). Let c be the constant in the lower
∆
−1
bound on ∆ in Lemma 2.3. For ε = c∆ · log n log 2 + log n , we obtain that ∆ ≥ c log n logε1/ε . Then


∆
applying Lemma 2.3 yields ∆ + ε∆ = ∆ + c log n log 2 + log
n colors. By Ghaffari et al. [GHK17a], we

know that THM (n, Γ, r) = O r 2 · log(nΓ) · log n · log4 Γ and thereby, the round complexity can be upper
bounded by

O ∆3 + ∆ · TWM (n, ∆, O(1/ε)) + logO(1) n



∆ log n
O(1/ε)
=O ∆ +
THM (n, ∆
, O (1/ε)) + logO(1) n
ε


∆8
3
4
O(1)
log
n
log
∆
+
log
n
= O ∆3 + ∆ ·
log8 n


= O ∆9 + logO(1) n .
3

3 Deterministic Distributed 3∆/2-Edge-Coloring
Let G = (V, E) be a graph with maximum degree at most ∆. There are two crucial points to compute a
3∆/2-edge-coloring of G: First, we can extract a so called (3)-graph H = (V, F ) from G and guarantee
that the maximum degree of the graph (V, E − F ) is at most ∆ − 2. Second, we can efficiently 3-color H.
Repeating these two steps ∆/2 times with a fresh set of colors for each extracted subgraph yields the result.
The extraction of (3)-graphs relies on the computation of a sequence of five maximal and maximum
matchings of subgraphs of G. While computing a maximum matching is a global problem in general bipartite graphs, we only compute maximum matchings in a special class of bipartite graphs. In these graphs the
maximum degree on one side is smaller than the minimum degree on the other side. (cf. Lemma 3.3).
We begin with the definition of (3)-graphs.
Definition 3.1. A (3)-graph is a graph with maximum degree 3 where no two degree-3 vertices are adjacent.
In it was shown by Fournier [Fou73] – via a global argument – that (3)-graphs admit 3-edge-colorings.
As the line graph of a (3)-graphs has maximum degree 3 the node coloring algorithm by Panconesi and
Srinivasan [PS95a, Theorem 3] colors the line graph with 3 colors, i.e., we can 3-edge-color (3)-graphs
with a distributed algorithm.
Lemma 3.1. (3)-graphs can be edge-colored in time O(log3 n) with 3 colors.
We continue with computing maximum matchings in certain bipartite graphs. More precisely, we can
efficiently compute maximum matchings if the minimum degree on one side of the graph is larger than the
maximum degree on the other side. We first bound the length of augmenting paths in such graphs. Notice
that in this section, we only consider unweighted graphs and therefore, we consider the standard version of
an “augmenting path”, i.e., a path with every second edge in a matching and non-matched endpoints.
Lemma 3.2. Assume we are given a bipartite graph B = (U, V, E), where all nodes in U have degree at
least d and all nodes in V have degree at most f < d. Further assume that we are given a matching M of
B and let S ⊆ U be the set of nodes in U that are not matched by M . Then, for each node s in S, there
exists an augmenting path of length at most O(d log n).
13

Proof. Consider the directed graph B ′ that is obtained from B by orienting all M -edges from V to U and
all other edges from U to V . A node s ∈ S has an augmenting path of length L iff in B ′ , there is a directed
path of length L from s to an unmatched node in V .
Fix some unmatched node s and assume that there is no augmenting path of length at most L. For i ≥ 0,
let Xi be the set of nodes in U that are within distance at most 2i from s in the directed graph B ′ . Further,
let Yi ⊆ V be the set of nodes that are within distance at most 2i + 1 from s in B ′ . As long as 2i + 1 ≤ L,
we have |Xi+1 | = |Yi | + 1 because we have the unmatched s ∈ Xi+1 and in addition, every node in Yi has
exactly one matched out-neighbor in Xi+1 . Because in the original bipartite graph B, every node in U has
at least d neighbors in V and every node in V has at most f ≤ d − 1 neighbors in U , we also have
|Yi | ≥ d/f · |Xi | ≥ d/(d − 1) · |Xi | .
Combining both facts, we thus have |Xi+1 | ≥ d/(d − 1) · |Xi | , if 2i + 1 ≤ L . If L ≥ cd log n for a
sufficiently large constant c, this leads to a contradiction.
Lemma 3.3. There is an O(d · log n · THM (n, dO(d log n) , d log n)) time distributed deterministic algorithm
˙ E) with
that computes a maximum matching in bipartite graphs G = (U ∪V,
d := min deg(u) > f := max deg(v) .
u∈U

v∈V

Proof. Augmenting paths can be seen as hyperedges of a hypergraph defined on the node set of G. We
consider augmenting paths with length up to ℓ = O(d log n), i.e, the hypergraph has rank at most ℓ and
degree at most dO(ℓ) . With this hypergraph correspondence at hand we iteratively compute maximal independent sets of shortest augmenting paths in time THM (n, dO(ℓ) , ℓ) [GHK17a]. A classic result [HK73]
shows that augmenting along a maximal independent set of augmenting paths increases the length of the
shortest augmenting path. Thus, using Lemma 3.2 we only need O(d log n) iterations of computing maximal independent sets of augmenting paths until we have computed a maximum matching.
Note that a maximum matching of a graph as in Lemma 3.3 matches all nodes in U .
Lemma 3.4 (Extracing (3)-graphs). Let G = (V, E) be a graph with maximum degree at most ∆ ≥ 3.
There is a deterministic distributed algorithm with time complexity
O(∆ · log n · THM (n, ∆O(∆ log n) , ∆ log n) + log3 n)
that computes an edge set F ⊆ E such that H = (V, F ) is a (3)-graph and the maximum degree of the
graph (V, E − F ) is at most ∆ − 2.
Algorithm: The algorithm consists of the following five steps in which we compute maximal and maximum
matchings of subgraphs of G. Note that maximal matchings can be computed in O(log3 n), [Fis17].
1. Let V∆ := {v ∈ S : degG (v) = ∆} be the nodes with maximum degree in G. Compute a maximal
matching M1 of G[V∆ ] and let G1 := (V, E − M1 ) be the graph that remains if we remove M1 .
2. Let V1,∆ := {v ∈ S : degG1 (v) = ∆} be the maximum degree nodes of G that have not been hit by M1 .
Let B1 be the bipartite subgraph of G1 that is spanned by V1,∆ and V − V1,∆ .
Compute a maximum matching M2 of B1 via Lemma 3.3 and let G2 := (V, E − M1 − M2 ) be the graph
that remains if we remove M2 from M1 .
3. Let V2,∆−1 := {v ∈ S : degG2 (v) = ∆ − 1} be the nodes that have degree ∆ − 1 in G2 .
Compute a maximal matching M3 of G2 [V2,∆−1 ] and define G3 := (V, E − M1 − M2 − M3 ).
4. Let V3,∆−1 := {v ∈ S : degG3 (v) = ∆ − 1} and let B3 be the bipartite subgraph of G3 that is spanned
by V3,∆−1 and V − V3,∆−1 .
Compute a maximum matching M4 of B3 via Lemma 3.3 and define H ′ := (V, M1 ∪ M2 ∪ M3 ∪ M4 ).
5. Compute a maximal matching M ′ of degree 3 nodes in H ′ and let H := (V, M1 ∪ M2 ∪ M3 ∪ M4 − M ′ ).
14

Proof of Lemma 3.4. We first prove that we can apply Lemma 3.3 in step two and four.
Step two: V1,∆ is an independent set in G1 because otherwise M1 would not be maximal. Thus, we have
that each of the ∆ edges adjacent in G1 to node v ∈ V1,∆ is an edge in B1 . That is,
d := min degB1 (v) = ∆ .
v∈V1,∆

By definition every node in V − V1,∆ has degree at most ∆ − 1 in G1 and also in B1 . Thus, we have
f :=

max

v∈(V −V1,∆ )

degB1 (v) ≤ ∆ − 1 .

Step four: V3,∆−1 is an independent set in G3 because otherwise M3 would not be maximal. Thus, we have
that each of the ∆ − 1 edges adjacent in G3 to node v ∈ V1,∆ is an edge in B3 . That is,
d :=

min

v∈V3,∆−1

degB3 (v) = ∆ − 1 .

By definition every node in V − V3,∆−1 has degree at most ∆ − 2 in G3 and also in B3 . Thus we have
f :=

max

v∈(V −V3,∆−1 )

degB3 (v) ≤ ∆ − 2 .

It is sufficient to show the following three properties: a) H is a (3)-graph. b) Every node with degree ∆
in G has at least degree two in H. c) Every node with degree ∆ − 1 in G has at least degree one in H.
Property a): The nodes of H have at most degree three: As M1 and M2 are matchings each node has
degree at most two in M1 ∪ M2 . In the third step only nodes with degree one in M1 ∪ M2 get at most one
additional edge, i.e., every node has at most two adjacent edges in M1 ∪ M2 ∪ M3 . In the fourth step we
add a single matching, i.e., every node has at most three adjacent edges in M1 ∪ M2 ∪ M3 ∪ M4 . In step 5
we only remove edges so the degree bound still holds.
The nodes of degree 3 in H form an independent set because we remove a maximal matching between
all degree three nodes in step 5.
Property b): A node with degree ∆ in G is hit at least once by M1 ∪ M2 because every node with degree
∆ in G which is not hit by M1 is for sure hit by the maximum matching M2 . If it was only hit once by
M1 ∪ M2 then it will be hit again at least once by M3 ∪ M4 . Furthermore, every node with degree at least
two in H ′ has degree at least two in H as well.
Property c): A node with degree ∆−1 in G is, if not hit by M1 ∪M2 ∪M3 , for sure hit by M4 . Furthermore,
any node which has degree at least one in H ′ has degree at least one in H.
Lemma 3.5. There is a deterministic distributed algorithm that computes a 3∆/2-edge-coloring
 of any
2
O(∆
log
n)
n-node graph with maximum degree at most ∆ in O ∆ · log n · THM (n, ∆
, Θ(∆ · log n)) rounds.

Proof. Let G0 := G = (V, E). We iteratively extract k = ⌊ ∆−1
2 ⌋ (3)-graphs H1 , H2 , . . . , Hk where the
(3)-graph Hi = (V, Fi ) is obtained by applying Lemma 3.4 to Gi−1 . We set Gi := (V, Ei ) = (V, Ei−1 −Fi ).
Then the edge sets F1 , . . . , Fk , Ek form a partition of E and we color each of the sets with a separate
set of colors as follows. Use Lemma 3.1 to edge-color each Hi , i = 1, . . . , k with a fresh set of three colors.
If ∆ is even, the maximum degree of Gk is at most two and we can color Gk with three colors with the
method by Cole and Vishkin [CV86] in time O(log∗ n). If ∆ is odd the maximum degree of Gk is at most
one and we can edge-color it with a single color in a single round. Altogether we use 3∆/2 colors and the
time complexity follows from the k invocations of Lemma 3.1 and Lemma 3.4.

15

4 Approximate Weighted Matching
In this section, we show that the CREW PRAM algorithm by Hougardy and Vinkemeier [HV06], which
approximates a weighted maximum matching, can be adapted to the distributed setting.
Augmentations. Let G = (V, E) be a graph with positive edge weights w : E → R+ . Let S and M be
matchings in G and consider the symmetric difference of S and M . We call S an augmenting path (resp.
cycle) of M if the symmetric difference is a path (resp. cycle) and S is a matching in E − M . Let M (S)
denote all the edges in M that have a node in common with S and w(S) the sum of edge weights in S (resp.
M ). For simplicity, we refer to both augmenting paths and cycles simply as augmentations. The number
of edges in an augmentation is referred to as its length and w(S) − w(M (S)) to as the gain of S. Notice
that the edges of matching M are not counted into the length of the augmentation. From here on, we only
consider augmentations of length at most ℓ = 2/ε and with positive gain.
Ranks. We divide the augmentations into ranks according to their gain. Let wmin and wmax be the minimum
and the maximum edge weights of G, respectively. We assume that both of these values are known to the
protocol. To later obtain a logarithmic number of ranks, we assume that wmax /wmin is polynomial in n.
For an augmentation S with gain g(S), the rank r(S) is defined as
1. r(S) = 0, if g(S) ≤

wmin
ℓ·n .

2. r(S) = i, where i is the smallest such that g(S) ≤ 2i ·

wmin
ℓ·n .

Notice that according to this definition, for any two augmentations of the same rank i > 0, the gain is within
a factor of 2. However, in the case of rank 0, this does not necessarily hold.
The case of small w(M ∗ ). For a technical reason, we perform a preprocessing step of O(1/ε) rounds,
where the nodes check if w(M ∗ ) < (1/ε)wmin . Notice that this can be the case only if the diameter of the
graph is at most 2/ε. In this case, we can simply choose a maximum matching as our output. Therefore, we
can assume for the rest of the section that w(M ∗ ) ≥ (1/ε)wmin .
To obtain a (1 − ε)-approximate weighted matching, our algorithm begins with an empty matching and
augments the matching O(1/ε) times with a maximal set of independent augmentations. To compute such
a set, we construct hypergraphs H1 , . . . , Hrmax on the node set V . The set of edges of Hi corresponds to
the augmenting paths and cycles of length at most ℓ with rank i with regard to the current matching. Then,
for i = rmax , . . . , 1, find a maximal matching in Hi . Before proceeding to Hi−1 , remove the matched
nodes in Hi from all Hj , j < i. Notice that the algorithm does not update the ranks of the augmentations
while we iterate through the hypergraphs. The union of the hypergraph matchings corresponds to the set of
augmentations which we use to augment the overall matching.
Differences to the approach by Hougardy and Vinkemeier [HV06]: Much of the above is along similar
ideas in [HV06]. However, the hypergraphs which we construct consists of augmentations which are formed
by paths and cycles whereas the corresponding part in [HV06] contains arbitrary augmentations, e.g., unions
of paths which are far away from each other in the network graph. In the LOCAL model it is not possible to
construct the hypergraphs efficiently if we allow those arbitrary augmentations. Secondly, our rank definition
differs slightly from the one in [HV06] (we use wmin instead of gmax ). Thirdly, we handle the case of small
w(M ∗ ) separately because due to the altered rank definition we will later use that w(M ∗ ) ≥ (1/ε)wmin
holds. Due to these changes we cannot use their analysis of the algorithm as a blackbox. However, almost
every line of the following analysis is similar to the proof by Hougardy and Vinkemeier.
Let us consider one iteration of our protocol, i.e., augmenting a matching M with the union of ranked
augmenting paths and cycles. Let M ∗ be a maximum weight matching in G and consider the symmetric
difference of M and M ∗ . Let C be a maximal cycle in this symmetric difference and let C ∗ = C ∩ M ∗ .
For the following definition, assume that the cycle is consistently oriented. We consider a multiset OPT that
contains ℓ copies of C ∗ if |C ∗ | ≤ ℓ and otherwise, for every edge e ∈ C ∗ , we insert an augmenting path of
16

length ℓ that contains e and the ℓ − 1 edges following e (according to the consistent orientation). In the case
that C is a path, we simply imagine that the endpoints are connected and handle C as in the case for cycles.
Now, by definition, any edge in M ∗ − M is contained in at least ℓ augmentations in OPT. Consider an
edge e ∈ M − M ∗ , that is part of a short path or cycle in the symmetric difference of M and M ∗ . For such
an edge, there are ℓ augmentations S ∈ OPT such that e is contained in M (S) (recall that in M (S) are the
edges of M that have a common node with S). For the case that e is part of a long cycle or path, it can be the
case that there are ℓ + 1 augmentations S ∈ OPT such that e is contained in M (S). In a cycle, for example,
e is connected to an augmentation in OPT that starts with an edge in front of e and to the ℓ augmentations
that contain the edge before e (again, according to the consistent orientation). We get that
X
g(S) ≥ ℓ · w(M ∗ ) − (ℓ + 1) · w(M ) .
(3)
S∈OPT

Recall, that we assumed that w(M ∗ ) ≥ (1/ε)wmin . Thus, if w(M ∗ ) − w(M ) < wmin , it holds that
w(M ) > w(M ∗ ) − wmin ≥ w(M ∗ ) − w(M ∗ )ε

and then the matching M is already a (1 − ε)-approximation. We can therefore assume that
wmin ≤ w(M ∗ ) − w(M ) .

Given the construction of OPT, we get that the number of augmentations in OPT is bounded by ℓ · n and by
identifying H0 with the set of corresponding augmentations, it follows that,
X
wmin
g(S) ≤ ℓ · n ·
≤ w(M ∗ ) − w(M ) .
(4)
n·ℓ
S∈OPT∩H0

In the next two lemmas we prove the approximation guarantee and finally, Lemma 2.5 follows by bounding
the runtime.
Lemma 4.1. Let M be a matching. Applying one iteration of our matching augmentations results in a
matching M ′ such that


1
ℓ−1
′
∗
w(M ) ≥ w(M ) +
·
(w(M ) − w(M )) .
4ℓ
ℓ
Proof. Consider some S ∈ OPT and assume r(S) = i > 0. Let ALG be the set of augmentations, i.e., the
hypergraph matching, computed by our algorithm. Since our algorithm picks maximal sets of hyperedges
with decreasing ranks, we get that ALG contains an augmentation, with rank i or higher and that has a node
common with augmentation S. If we assign S to such a node, we get due to the definition of OPT that at
most ℓ augmentations are assigned per node. Recall that the length of an augmentation S, that is a matching,
corresponds to the number of edges in S. Thus, the edges of an augmentation of length at most ℓ are incident
on at most 2ℓ nodes. Let OPT>0 ⊆ OPT be the augmentations of rank higher than 0. It follows that
X
11 1 X
1
g(ALG) ≥
g(S) .
(5)
g(S) ≥ 2
2 ℓ 2ℓ
4ℓ
S∈OPT>0

S∈OPT>0

We can use Eqs. (3) and (4) to obtain
X
X
X
g(S) =
g(S) −
S∈OPT>0

S∈OPT

g(S)

S∈OPT∩H0

Eq. (3)
≥ ℓ · w(M ∗ ) − (ℓ + 1) · w(M ) −

X

g(S)

S∈OPT∩H0

Eq. (4)
≥ ℓ · w(M ∗ ) − (ℓ + 1) · w(M ) − w(M ∗ ) − w(M ) = (ℓ − 1) · w(M ∗ ) − ℓ · w(M ) .
17

Combining with Equation (5), we get that
1
1
g(ALG) ≥ 2 · ((ℓ − 1) · w(M ∗ ) − ℓ · w(M )) = 2 · ℓ ·
4ℓ
4ℓ


1
ℓ−1
=
·
(w(M ∗ ) − w(M )) .
4ℓ
ℓ




ℓ−1
∗
(w(M ) − w(M ))
ℓ

Finally, the result follows from the fact that g(ALG) = w(M ′ ) − w(M ),
Lemma 4.2. Let G be an edge-weighted graph and assume that wmin is known to the nodes. Then, for every
ε > 0, there is a deterministic distributed algorithm that finds a matching M such that
w(M ) ≥ (1 − ε)w(M ∗ ) .
Proof. Let M0 be an empty matching and Mi a matching obtained by applying one iteration of the augmentations from the hypergraph matching procedure. By Lemma 4.1, we get that


ℓ−1
1
∗
·
w(M ) − w(Mi ) .
w(Mi+1 ) ≥ w(Mi ) +
4ℓ
ℓ
Solving this recurrence (c.f. [HV06, Proof of Theorem 2]) yields that for some k ∈ O(1/ε) we get that
w(Mk ) ≥ (1 − ε)w(M ∗ ).
Proof of Lemma 2.5. Constructing the hypergraphs H1 , . . . , Hrmax for a single augmentation can be done in
parallel in O(ℓ) rounds. By definition, we get that the number of nodes per hyperedge (i.e., the hyperedge
rank) in H is bounded from above by ℓ. Notice that one round of communication in this hypergraph can
take up to ℓ rounds, since the nodes adjacent in the hypergraph might be up to ℓ hops away in the underlying
communication graph. Given that wmax /wmin ∈ nO(1) and ℓ ≤ n, we get that rmax ∈ O(log n). The degree
of each hypergraph is upper bounded by ∆O(ℓ) . Therefore, iterating through the hypergraphs and finding a
maximal matching in each of them can be done in


O ℓ · THM (n, ∆O(ℓ) , ℓ) · log n

rounds where THM (n, Γ, r) is the time of an algorithm which solves the maximal matching algorithm on a
hypergraph with n nodes, maximum degree at most Γ and rank r.
Once the augmentation has been computed, they can be applied in time O(ℓ) = O(1/ε). As we iteratively compute O(1/ε) augmentations the total round complexity is




O (1/ε) · ((1/ε) + THM (n, ∆O(ℓ) , ℓ) · log n) = O 1/ε2 + (1/ε) · THM (n, ∆O(ℓ) , ℓ) · log n .

The result follows by applying Lemma 4.2 and completing the matching into a maximal matching in time
O(log3 n) with the algorithm by Fischer [Fis17].

5 Derandomizing Randomized Edge-Coloring Algorithms
In [GHK17a], Ghaffari, Harris, and Kuhn have recently developed generic methods to derandomize distributed algorithm in the LOCAL model. We next describe how these techniques can be applied in a blackbox way to existing randomized in order to get deterministic polylogarithmic time edge-coloring algorithms.
A special case of Theorem 1.1 in [GHK17a] immediately gives the following generic distributed derandomization result.

18

Lemma 5.1 (Special case of Theorem 1.1 in [GHK17a]). Let G = (V, E) be an n-node graph with maximum degree ∆. Any r-round randomized LOCAL algorithm for a locally checkable problem on G can be
transformed to a deterministic LOCAL algorithm on G with time complexity O r · (∆O(r) + log∗ n) .

A problem is called locally checkable if the correctness of a solution can be checked in O(1) rounds in
the LOCAL model: If the solution is correct, all nodes output “yes”, if the solution is not correct, at least
one node must output “no” (cf. [FKP13]). We apply the above lemma to the randomized edge-coloring
algorithm of [CHL+ 18], where the following statement is proven.
Lemma 5.2 (Theorem 3.1 in [CHL+ 18]). Let G = (V, E) be an n-node graph with maximum degree ∆

2.5
and let ε = ω log√∆ ∆ be a function of ∆. If ∆ > ∆ε is sufficiently large, an (1 + ε)∆-edge coloring of G
can be computed in the time required to solve
a) O(log(1/ε)) instances of a symmetric Lovász Local Lemma (LLL) problem on an n-vertex dependency
O(1) and where each of the bad events occurs with probability at most
graph with maximum degree
 ∆
4+o(1)
2
exp − ε ∆/ log
∆ , as well as
b) one instance of an O(ε∆)-edge coloring problem on a graph of maximum degree O(ε∆).
Combining the two lemmas with the randomized distributed LLL algorithm of [CPS17] and the distribouted degree splitting algorithm of [GHK+ 17b], we obtain the following theorem.

2.5
Theorem 5.3. Let G = (V, E) be an n-node graph with maximum degree at most ∆ and let ε = ω log√∆ ∆ .
4+o(1)

n)
for a sufficiently large constant c > 0, there exists a deterministic distributed
If ∆ ≥ c · log n · (logεlog
2
algorithm to compute a (1 + ε)∆-edge coloring of G in (log(n)/ε)O(1) rounds.

Proof Sketch. We here show how to get a deterministic edge coloring algorithm with time complexity
∆O(1) + O(log∗ n). A time complexity of (log(n)/ε)O(1) can then be achieved by using the degree splitting
algorithm of [GHK+ 17b], in the same way as we did in the proof of Theorem 1.1, by effectively reducing
n)4+o(1) 
the maximum degree to Θ log n · (logεlog
.
2
4+o(1)

n)
for a sufficiently large constant c > 1. We use Lemma 5.1
Assume that ∆ ≥ c · log n · (logεlog
2
to derandomize the solution of each of the LLL instances in the randomized edge coloring algorithm of
Lemma 5.2. The best randomized distributed LLL in our context is from the work of Chung, Pettie, and
Su [CPS17]. Assume that we are given an n-vertex dependency graph with maximum degree d and where
each bad event has probability at most p. If epd2 < 1, the algorithm of [CPS17] computes a solution

in time O(log(n)/ log(1/epd2 )). In our case, we have d = ∆O(1) and p = exp − ε2 ∆/ log4+o(1) ∆ .
Hence, we have epd2 = exp(−Θ(log n)) and the LLL algorithm of [CPS17] thus has a constant time
complexity. Using Lemma 5.1, we can therefore turn the randomized LLL algorithm into a deterministic
distributed algorithm with time complexity ∆O(1) + O(log∗ n). In the last step of the randomized edge
coloring algorithm of [CHL+ 18], one needs to compute an O(ε∆)-edge coloring on a graph of maximum
degree O(ε∆). This can be done deterministically in time O(∆ + log∗ n) by using the (∆ + 1)-vertex
coloring algorithm of [BEK15].

19

References
[ABI86]

N. Alon, L. Babai, and A. Itai. A fast and simple randomized parallel algorithm for the
maximal independent set problem. J. of Algorithms, 7(4):567–583, 1986.

[Alo03]

N. Alon. A simple algorithm for edge-coloring bipartite multigraphs. Information Processing
Letters, 85(6):301–302, 2003.

[Bar15]

L. Barenboim. Deterministic (∆ + 1)-coloring in sublinear (in ∆) time in static, dynamic and
faulty networks. In Proc. 34th ACM Symp. on Principles of Distributed Computing (PODC),
pages 345–354, 2015.

[BE11]

L. Barenboim and M. Elkin. Distributed deterministic edge coloring using bounded neighborhood independence. In Proc. 30th Symp. on Principles of Distributed Computing (PODC),
pages 129–138, 2011.

[BE13]

L. Barenboim and M. Elkin. Distributed Graph Coloring: Fundamentals and Recent Developments. Morgan & Claypool Publishers, 2013.

[BEK15]

L. Barenboim, M. Elkin, and F. Kuhn. Distributed (∆ + 1)-coloring in linear (in ∆) time.
SIAM J. Computing, 43(1):72–95, 2015.

[BEM17]

L. Barenboim, M. Elkin, and T. Maimon. Deterministic distributed (Delta + o(Delta))-edgecoloring, and vertex-coloring of graphs with bounded diversity. In Proc. 36th ACM Symp. on
Principles of Distributed Computing (PODC), pages 175–184, 2017.

[BEPS12]

L. Barenboim, M. Elkin, S. Pettie, and J. Schneider. The locality of distributed symmetry
breaking. In Proc. 53th Symp. on Foundations of Computer Science (FOCS), pages 20:1–
20:45, 2012.

[Bol98]

B. Bollobas. Modern Graph Theory. Springer, 1998.

[CH03]

Andrzej Czygrinow and Michał Hańćkowiak. Distributed algorithm for better approximation
of the maximum matching. In International Computing and Combinatorics Conference, pages
242–251, 2003.

[CHK01]

A. Czygrinow, M. Hańćkowiak, and M. Karoński. Distributed O(∆ log n)-edge-coloring algorithm. In Proc. 9th European Symposium on Algorithms (ESA), pages 345–355, 2001.

[CHL+ 18]

Y.-J. Chang, Q. He, W. Li, S. Pettie, and J. Uitto. The complexity of distributed edge coloring
with small palettes. In Proc. 29th ACM-SIAM Symp. on Discrete Algorithms (SODA), 2018.
arXiv:1708.04290.

[CPS17]

K.-M. Chung, S. Pettie, and H.-H. Su. Distributed algorithms for the Lovász local lemma and
graph coloring. Distributed Computing, 30(4):261–280, 2017.

[CV86]

R. Cole and U. Vishkin. Deterministic coin tossing with applications to optimal parallel list
ranking. Information and Control, 70(1):32–53, 1986.

[EPS15]

M. Elkin, S. Pettie, and H.-H. Su. (2∆ − 1)-edge-coloring is much easier than maximal
matching in the distributed setting. In Proc. 26th ACM-SIAM Symp. on Discrete Algorithms
(SODA), pages 355–370, 2015.

[FGK17]

M. Fischer, M. Ghaffari, and F. Kuhn. Deterministic distributed edge-coloring via hypergraph
maximal matching. In Proc. 58th IEEE Symp. on Foundations of Computer Science (FOCS),
2017. arXiv:1704.02767.
20

[FHK16]

P. Fraigniaud, M. Heinrich, and A. Kosowski. Local conflict coloring. In Proc. 57th IEEE
Symp. on Foundations of Computer Science (FOCS), pages 625–634, 2016.

[Fis17]

M. Fischer. Deterministic distributed matching: Simpler, faster, better. In Proc. 30th Symp. on
Distributed Computing (DISC), pages 17:1–17:15, 2017.

[FKP13]

P. Fraigniaud, A. Korman, and D. Peleg. Towards a complexity theory for local distributed
computing. J. of the ACM, 60(5):35, 2013.

[Fou73]

J.-C. Fournier. Colorations des arêtes d’un graphe. Cahiers du Centre d’tudes de Recherche
Oprationnelle, 15:311–314, 1973.

[GHK17a]

M. Ghaffari, D. G. Harris, and F. Kuhn. On Derandomizing Local Distributed Algorithms.
ArXiv e-prints, November 2017.

[GHK+ 17b] M. Ghaffari, J. Hirvonen, F. Kuhn, Y. Maus, J. Suomela, and J. Uitto. Improved distributed
degree splitting and edge coloring. In Proc. 30th Symp. on Distributed Computing (DISC),
pages 19:1–19:15, 2017.
[GS17]

M. Ghaffari and H.-H. Su. Distributed degree splitting, edge coloring, and orientations. In
Proc. 28th ACM-SIAM Symp. on Discrete Algorithms (SODA), 2017. arXiv:1608.03220.

[HK73]

J. E. Hopcroft and R. M. Karp. An n5/2 algorithm for maximum matchings in bipartite graphs.
SIAM J. Comput., 2(4):225–231, 1973.

[HSS16]

S. G. Harris, J. Schneider, and H.-H. Su. Distributed (∆ + 1)-coloring in sublogarithmic
rounds. In Proc. 48th Symp. on the Theory of Computing (STOC), pages 465–478 465–478
465–478, 2016.

[HV06]

S. Hougardy and D. E. Vinkemeier. Approximating weighted matchings in parallel. Information Processing Letters, 99(3):119–123, 2006.

[Lin92]

N. Linial. Locality in distributed graph algorithms. SIAM Journal on Computing, 21(1):193–
201, 1992.

[LPSP08]

Z. Lotker, B. Patt-Shamir, and S. Pettie. Improved distributed approximate matching. In Proc.
of the 20th Annual Symposium on Parallelism in Algorithms and Architectures (SPAA), pages
129–136, 2008.

[Lub86]

M. Luby. A simple parallel algorithm for the maximal independent set problem. SIAM Journal
on Computing, 15(4):1036–1053, 1986.

[PR01]

A. Panconesi and R. Rizzi. Some simple distributed algorithms for sparse networks. Distributed computing, 14(2):97–100, 2001.

[PS92]

A. Panconesi and A. Srinivasan. Fast randomized algorithms for distributed edge coloring.
In Proc. 11th ACM Symp. on Principles of Distributed Computing (PODC), pages 251–262,
1992.

[PS95a]

A. Panconesi and A. Srinivasan. The local nature of ∆-coloring and its algorithmic applications. Combinatorica, 15(2):255–280, Jun 1995.

[PS95b]

A. Panconesi and A. Srinivasan. On the complexity of distributed network decomposition.
Journal of Algorithms, 20(2):581–592, 1995.

[Viz64]

V. G. Vizing. On an estimate of the chromatic class of a p-graph. Diskret analiz, 3:25–30,
1964.

21

