Authors Bahman Bahmani, Aranyak Mehta, Rajeev Motwani,
License CC-BY-3.0
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 567–595
www.theoryofcomputing.org
S PECIAL ISSUE IN HONOR OF R AJEEV M OTWANI
Online Graph Edge-Coloring in the
Random-Order Arrival Model∗
Bahman Bahmani† Aranyak Mehta Rajeev Motwani
Received: July 31, 2010; published: December 9, 2012.
Abstract: A classic theorem by Vizing asserts that if the maximum degree of a graph
is ∆, then it is possible to color its edges, in polynomial time, using at most ∆ + 1 colors.
However, this algorithm is offline, i. e., it assumes the whole graph is known in advance. A
natural question then is how well we can do in the online setting, where the edges of the
graph are revealed one by one, and we need to color each edge as soon as it is added to
the graph. Online edge coloring has an important application in fast switch scheduling. A
natural model is that edges arrive online, but in a random permutation. Even in the random
permutation model, the best proven approximation factor for any algorithm is the factor 2
of the simple greedy algorithm (which holds even in the worst-case online model). The
algorithm of Aggarwal et al. (FOCS’03) provides a 1+o(1) factor algorithm for the case
of very dense multi-graphs, when ∆ = ω(n2 ), where n is the number of vertices. In this
paper, we show that for graphs with ∆ = ω(log n), it is possible to color the graph with
1 + e/(e2 − 1) + o(1) ∆ ≤ 1.43∆ colors, with high probability, in the online random-order
model. Our algorithm is inspired by a 1.6-approximate distributed offline algorithm of
Panconesi and Srinivasan (PODC’92), which we extend by reusing failed colors online.
∗ A preliminary version of this paper appeared in the Proceedings of the Twenty-First Annual ACM-SIAM Symposium on
Discrete Algorithms (SODA 2010).
† Supported by a Stanford Graduate Fellowship.
ACM Classification: F.2.2, G.2.2
AMS Classification: 05C85, 68W27, 68R10
Key words and phrases: graph edge coloring, online algorithm, random order
2012 Bahman Bahmani, Aranyak Mehta, and Rajeev Motwani
Licensed under a Creative Commons Attribution License DOI: 10.4086/toc.2012.v008a025
BAHMAN BAHMANI , A RANYAK M EHTA , AND R AJEEV M OTWANI
Further, we show how we can extend the algorithm to reuse colors multiple times, which
reduces the approximation factor below 1.43. We conjecture that the algorithm becomes
nearly optimal (i. e., uses ∆ + o(∆) colors) with O(log (∆/ log n)) reuses. We reduce the
question to proving the non-negativity of a certain recursively defined sequence, which
looks true in computer simulations. This non-negativity can be proved explicitly for a small
number of reuses, giving improved algorithms: e. g., the algorithm which reuses colors 5
times uses 1.26∆ colors.
1 Introduction
An edge coloring of a graph is a coloring of its edges so that no two edges incident on each other get the
same color. If the maximum degree of a graph is ∆, then obviously, every edge coloring needs at least
∆ colors. A classic theorem by Vizing [9] proves that it is possible to edge-color a graph using at most
∆ + 1 colors. However, determining whether the required number of colors is ∆ or ∆ + 1 is known to be
NP-complete for general graphs [7]. The proof of Vizing’s theorem is constructive and actually gives a
polynomial time algorithm to find an edge coloring using at most ∆ + 1 colors. For bipartite graphs there
are fast algorithms to edge color using ∆ colors [3]. However, all these algorithms are offline, i. e., they
assume that the graph is known in advance. A natural question then is how well we can do in the online
setting, where the edges of the graph are revealed one by one, and we need to color each edge as soon as
it is added to the graph.
We study the online edge coloring problem for bipartite graphs, in the model in which edges arrive
in a random permutation.1 We also assume that the graph is regular (otherwise, one can add dummy
edges to the graph to make it regular [1]). We note that the random order arrival model can simply be
considered as an algorithmic technique for fast offline approximation: randomly permute the edges and
run a (simple and local) online algorithm.
1.1 Problem definition
Let G = (B, T, E) be a regular bipartite graph with degree ∆. Throughout, we will call the vertices in B as
bottom vertices, and the vertices in T as top vertices. The vertices are known in advance, while the edges
E are unknown. Edges arrive online in a random permutation of E. We have to color each edge as soon
as it arrives, so as to get a valid edge coloring at the end of the algorithm. The objective is to do this using
the smallest number of colors possible.
1.2 Prior work and our results
Prior work The simple greedy algorithm (Greedy), which colors each edge with the smallest color
(in some fixed but arbitrary numbering of colors) not already used by a neighboring edge, will color the
graph with no more than 2∆ − 1 colors. This is true in the worst-case online model, with adversarial input
order on E. But in fact, this is the best known analysis for Greedy even in the random-order arrival model.
1 Note that, as shown in [8], the edge coloring problem for non-bipartite graphs can be reduced to the problem for bipartite
graphs, by considering a random balanced cut in the graph, coloring the edges of the cut, and then recursing on the two sides of
the cut. Note that this can be done in the online setting as well.
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 567–595 568
O NLINE G RAPH E DGE -C OLORING IN THE R ANDOM -O RDER A RRIVAL M ODEL
∆ # colors used Arrival order
Greedy Algorithm no constraint ≤ 2∆ − 1 Adversarial
√
Lower Bound [2] O log n ≥ 2∆ − 1 Adversarial
Algorithm [1] ω(n2 ) ∆ + o(∆) Random
Here (Extension to 5 rounds) ω(log n) 1.26∆ Random
Figure 1: A summary of known upper and lower bounds in the Adversarial and Random-Order models
Bar-Noy et al. [2] prove that Greedy is optimal for both deterministic and randomized algorithms in
the worst-case order model. However, the examples they construct to prove the lower bounds are very
√
sparse, i. e., ∆ = O(log n) for deterministic algorithms, and ∆ = O( log n) for randomized algorithms.
Then, the natural question is can we do better than Greedy if the graph is “dense.”
Aggarwal et al. [1] gave an online algorithm which colors a bipartite graph using ∆+o(∆) colors in the
random-order arrival model, when ∆ = ω(n2 ). Thus, this achieves essentially optimal performance, but in
an extremely dense multigraph. The motivation in [1] to study bipartite edge coloring in the random-order
model was an application in high-speed switch scheduling. We point to [1] and the references therein for
details, and provide only a brief outline of the application here. The input and output ports of a switch
correspond to the two sides of a bipartite graph. At every time step, at most one request arrives at each
input port, destined to some output port. Also, at each time step the switch can route a matching across
from input to output ports: at most one packet leaving each input port and at most one arriving at each
output port. A fast edge coloring algorithm which uses ∆ + o(∆) colors for a graph of degree ∆ can be
used to schedule the switch as follows: for some ∆ number of time steps, color each incoming request as
an edge in the graph. Then spend the next ∆ + o(∆) time steps routing the matchings corresponding to
each color class from the edge-coloring, and at the same time coloring the newly incoming requests as
the edges of a new graph. In this application, an algorithm which works with the density bound of ω(n2 )
suffices, while causing a delay of ω(n2 ) per packet. An algorithm with a smaller density bound will also
work, and will reduce the wait time of each request, provided it uses ∆ + o(∆) colors. We further discuss
the connection of our algorithm to the one in [1] in Section 4.
Thus, no algorithm is known to perform better than Greedy’s factor 2 (using fewer than 2∆ − 1 col-
ors) even in the random-order arrival online model, when the graph is denser than log n, but sparser than n2 .
Our results In this paper, we provide an online algorithm which uses
e
1+ 2 ∆ + o(∆) < 1.43∆
e −1
colors, with high probability, for graphs with ∆ = ω(log n). We briefly describe the algorithm here (a
detailed description is provided in Section 2): The algorithm has a number of palettes Pi , each with a
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 567–595 569
BAHMAN BAHMANI , A RANYAK M EHTA , AND R AJEEV M OTWANI
different number of colors. It partitions the incoming edges into two types, “Early” and “Late,” depending
on the arrival time of the edge. For an early edge (b,t), the algorithm tries to color it with a random
color from P1 which b has not tried before. If it fails (because some previously arrived edge incident on t
has used that color already), then it tries to color it with a random color from P2 which b has not tried
before, and so on, until success. After all the early edges have arrived, a subset Ri (b) of colors from Pi
have failed to be used by each bottom vertex b. The algorithm augments this set by injecting a set of new
colors Ni so that we have a sufficient number of colors. Then, for a late edge (b,t), the algorithm tries
to color it using a random color chosen from R1 (b) ∪ N1 which b has not tried before for a late edge. If
it fails to do so, it will try to color the edge with a random color from R2 (b) ∪ N2 (not tried by b for a
late edge), and so on. Thus, the main idea in the algorithm is to reuse failed colors: each color from the
palettes Pi gets a second chance (at each bottom vertex) before it is discarded.
Analysis techniques One of the main difficulties in the analysis of the algorithm lies in the correlations
between the sets of reusable colors at bottom and top vertices when we process late edges. For example,
it could be that bottom vertices can only use precisely those colors for late edges which the incident
top vertices have already used up to color some early edges. In this pessimistic case, when the sets of
available colors at bottom and top vertices are disjoint, we would not be able to reuse any colors and
would get a factor of e/(e − 1) ' 1.59. In the optimistic case, these sets of reusable colors are identical
for all vertices, and the analysis would proceed to give a factor of e2 /(e2 − 1) ' 1.16. If the sets were
independent, we would get a factor of (e2 + e − 1)/(e2 − 1) ' 1.43. What we prove is that these sets
are positively correlated for bottom and top vertices, which still leads to the same 1.43 factor. Figure 2
provides an example to describe the importance of the correlation between reusable colors at bottom and
top vertices in Round 2. In our analysis, we do not need to make any assumptions on the correlations
between available colors at different bottom vertices.
A related issue is that, due to the non-independence of the reusable color sets, late edges can have
unequal probabilities of succeeding to color themselves from different palettes (as opposed to early edges,
where the probability of success depends only on the position in the random permutation). For example,
due to the structure of the graph, some vertices may be “lucky” in the sense that their late edges succeed
in coloring themselves from the first few palettes. While this is a good event as such, it leads to an
uneven and unwieldy analysis. We rectify this by smoothing out success probabilities at every edge by
artificially rejecting edges which succeed more than required, by flipping a coin with an appropriate bias.
We provide an example in Section 2.3 (Figure 4 in Remark 2.11) to illustrate the reason probabilities of
success can be different for different round 2 edges, even if they are incident on the same top vertex.
Extension We may hope to use a smaller number of colors by extending the algorithm to allow bottom
nodes to possibly try each color more than two times. In Section 3, we show how we can extend the
algorithm by dividing the edges to multiple rounds (instead of just two rounds, early and late). We
show that by doing so we can indeed improve the approximation factor, and we conjecture that with
O(log(∆/ log n)) rounds, the algorithm uses a near-optimal ∆ + o(∆) colors. We reduce this question to
proving that a certain recursively defined numeric sequence is non-negative. This seems to be true from
computer simulations. The non-negativity question can be resolved explicitly for small number of rounds,
which gives, e. g., a 5-round algorithm using 1.26∆ colors.
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 567–595 570
O NLINE G RAPH E DGE -C OLORING IN THE R ANDOM -O RDER A RRIVAL M ODEL
Figure 2: This example illustrates how the probability of successful coloring of round 2 edges depends on
the correlation between the set of colors available at top and bottom vertices. E 1 (t) is the set of colors
available at top vertex t, and R1 (b), R1 (b0 ) are the sets available at bottom vertices b, b0 . In the example
on the left, since R1 (b) ∪ E 1 (t) = 0/ and R1 (b0 ) ∪ E 1 (t) = 0,
/ the round 2 edges (b,t) and (b0 ,t) have zero
chance each of being colored successfully. In the example on the right, R1 (b) = R1 (b0 ) = E 1 (t), so both
the edges have a (constant) positive probability of success. (For simplicity, we have ignored the existence
of the new palette N1 in round 2 in this example.)
1.3 Previous related results on distributed algorithms
There is a related sequence of results in the literature on distributed offline algorithms for edge coloring.
The first such algorithm with a factor less than 2 was provided by Panconesi and Srinivasan [8] (we will
refer to the algorithm as PS), which uses (e/(e − 1))∆ ' 1.59∆ colors. Since our algorithm is inspired
by PS, we describe it at some length here. PS runs in phases, where each phase has its own palette of
colors. In each phase, each bottom vertex proposes colors for all its incident edges by taking a random
permutation of the colors in the palette for that phase. Thus there are no color conflicts of proposed colors
at bottom vertices. In the same phase, each top vertex accepts, for each color, exactly one incident edge
chosen uniformly at random among those which propose that color. If an edge gets its proposed color
accepted, then its color is fixed. Otherwise, it proceeds to the next phase. This propose-accept process
guarantees that there are no color conflicts at any vertex. In each phase, some fraction of each vertex’s
incident edges get colored. It is proved that, with high probability, the vertex degrees reduce at a rate of
1/e, giving a total number of 1/(1 − 1/e) ≈ 1.58∆ colors.
Our online algorithm is inspired by PS. Firstly, we show how to convert the idea behind PS to work
in the online random-order setting. Secondly (and this is our main algorithmic contribution) we introduce
the idea of reusing colors of a palette which a bottom vertex failed to use, in a next round (for edges which
arrive later in the online order). So, at a high level (as will become clear in Section 2), our first round
implements PS online for edges which arrive early, and the second round reuses the failed colors for late
edges. We note that Aggarwal et al. [1] mention in their introduction that PS can be made online to use
1/(1 − 1/e) colors, although no details are given (presumably they meant a transformation similar to
ours). Subsequent to [8], distributed algorithms were found [4, 6] using a near-optimal ∆ + o(∆) number
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 567–595 571
BAHMAN BAHMANI , A RANYAK M EHTA , AND R AJEEV M OTWANI
of colors (for ∆ = Ω(polylog(n))). However, it is unclear how to make those algorithms work in the
online model. As a related reference, we note the book [5], which includes a clear exposition of the
concentration of measure techniques used in the analysis of these distributed algorithms.
2 The two round algorithm
The online algorithm is defined in Figure 3. Let r = e/(e + 1). We partition the input edges into two
types: edges that arrive before time rn∆ are called Round 1 (or Early) edges, and edges which arrive later
than time rn∆ are called Round 2 (or Late) edges. The algorithm has a collection of L = O(log (∆/ log n))
main palettes P1 , P2 , P3 , . . . , PL , as well as L augmenting palettes N1 , N2 , N3 , . . . , NL , each with a
distinct set of colors. Palette Pi has size ∆(i) where ∆(i) is recursively defined by: ∆(1) = r∆ − o(∆), and
∆(i+1) = ∆(i) /e − o(∆(i) ). The size of the palette Ni will be determined later. The algorithm also has a
special palette, P∞ , with o(∆) colors.
Round 1 edges are treated as follows: For each bottom vertex b and each i ∈ [1, L], we maintain a
set Triedi (b) ⊆ Pi , which is the set of colors from Pi that b has already proposed for any of its incident
edges. When a round 1 edge (b,t) arrives, we try to color it using a random color c∗ from P1 \ Tried1 .
If no previously arrived edge (b0 ,t) was already colored c∗ , then we succeed in coloring (b,t) with c∗ .
Otherwise, we fail to color (b,t) from P1 and we try from P2 \ Tried2 , and so on. If we fail to color (b,t)
from all palettes P1 , . . . , PL , then we greedily color (b,t) using P∞ .2 For each b and each i ∈ [1, L], we
also maintain Ri (b) ⊆ Pi , which is the set of colors from Pi which b tried to use to color some Round 1
edge (b,t), but failed because some previously arrived edge (b0 ,t) had already taken that color.
Round 2 edges are treated in a similar manner, but with two differences:
(1) For every bottom vertex b, and for every i = 1, . . . , L, we replace Pi with Ri (b) Ni . Thus each
S
bottom vertex reuses the colors Ri (b) it failed to use in Round 1. The palette Ni is added to provide
enough additional colors to have a proposal for every round 2 edge.
(2) A top vertex may reject some proposals, even if there is no previously arrived incident edge which
has used that color. This is done randomly by flipping a coin of an appropriate bias, and is done so
that the probability that an edge succeeds in coloring itself from Ri (·) ∪ Ni depends only on the
position within the permutation and not on the identity of the edge. We describe the motivation
and the details of this artificial rejection, including the definitions of qi (h) and pi (t, h) (as used in
Figure 3), in detail in Section 2.3.
It is easy to see that the algorithm produces a valid coloring, i. e., it never uses the same color for
two edges incident on each other: (1) bottom vertices propose colors for their edges by sampling without
replacement, so there is no color conflict at bottom vertices, (2) we accept a proposed color only if no
previously arrived edge incident on the same top vertex has already been colored that color. We will
prove that, by choosing the right values for | Ni |, with high probability, the algorithm does not abort in
2 As a minor point, we also color (b,t) from P∞ if it fails to get colored from P1 , . . . , Pi , but there are already at least ∆(i+1)
edges incident on t which have failed to get colored from P1 , . . . , Pi (for some i ∈ [1, L − 1]). This is done to just make some of
the later analysis a bit cleaner.
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 567–595 572
O NLINE G RAPH E DGE -C OLORING IN THE R ANDOM -O RDER A RRIVAL M ODEL
Round 1 (Early edges):
For all i ∈ [1, L], bottom nodes b, and top nodes t, initialize Triedi (b) = Ri (b) = 0,
/ and degi1 (t) = 0.
For s ∈ [1, rn∆], when the sth edge e = (b,t) arrives in the online order:
• Set i = 0.
• While (e is not colored and i < L):
– i + +.
– degi1 (t) + +.
– If degi1 (t) > ∆(i) :
∞
* Color e greedily from P ; If that is not possible, then abort.
– Else:
∗ i i i i ∗
* Pick a color c uniformly at random from P \ Tried (b). Set Tried (b) = Tried (b) ∪ {c }.
(If no such color exists then continue).
∗ ∗
* If no previously arrived edge incident on t was colored c , then color e with c ;
Else set R (b) = R (b) ∪ {c∗ }.
i i
• If e is not yet colored, color it greedily from P∞ . If no such color is available in P∞ , then abort.
Round 2 (Late edges):
For all bottom vertices b and all i ∈ [1, L], initialize Triedi (b) = 0.
/
For s ∈ [rn∆ + 1, n∆], when the sth edge e = (b,t) arrives in the online order:
• Set i = 0.
• While (e is not colored and i < L):
– i + +.
– Pick a color c∗ uniformly at random from Ri (b) ∪ Ni \ Triedi (b). Set Triedi (b) = Triedi (b) ∪
{c∗ }. (If no such color exists then continue).
– If no previously arrived edge incident on t has proposed c∗ , then
(a) If c∗ ∈ Ni then color e with c∗ .
(b) If c∗ ∈ Ri (b), and e = (b,t) is the hth edge incident on t proposing from a phase i palette
i (h)
(namely Ri (b) ∪ Ni ), then color e with c∗ with probability pqi (t,h) .
• If e is not yet colored, color it greedily from P∞ . If no such color is available in P∞ , then abort.
Figure 3: The Online Algorithm
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 567–595 573
BAHMAN BAHMANI , A RANYAK M EHTA , AND R AJEEV M OTWANI
the last step, i. e., each edge gets colored from one of the palettes. The total number of colors used is then
L L
∑ | Pi | + ∑ | Ni | + | P∞ | .
i=1 i=1
The analysis is in three steps: Firstly, we bound the number of colors used for round 1 edges, and
prove correlations between the sets of rejected colors at different vertices (Section 2.1). Secondly, we
bound the number of colors used for round 2 edges (Section 2.3). Finally we put all the bounds together
to get the full count of the number of colors used (Section 2.4).
But, before proceeding to the analysis, we first give some notation and definitions that will be useful
later.
Definition 2.1. We say that a vertex or an edge reaches phase i if it chooses a color from Pi (for a round 1
edge) or from Ri (·) ∪ Ni (round 2 edge). For any vertex v (top or bottom), i ∈ [1, L], and j ∈ {1, 2} define
degij (v) as the number of Round j edges incident on v which propose a color in phase i. Also, for any top
vertex t, i ∈ [1, L], j ∈ {1, 2}, and h ∈ 1, degij (t) , define eij (t, h) to be the hth edge (in the arrival order)
incident on t in round j, which proposes a color in phase i. As a matter of notation, throughout we will
use the term “with high probability” (or “w. h. p.”) to mean “with probability at least 1 − poly(1/n),” and
we will use ∼ to denote “equal up to higher order terms.”
2.1 Round 1 analysis
In this section, we analyze Round 1 of the algorithm. Recall the recursive definition ∆(i+1) = ∆(i) /e −
o(∆(i) ), with ∆(1) = r∆ − o(∆).
Lemma 2.2. For all i ∈ [1, L], t ∈ T and h ∈ [1, degi1 (t)], the probability that ei1 (t, h) is colored with a
h−1
color from Pi is 1 − 1/∆(i) .
Proof. ei1 (t, h) gets accepted if and only if none of the previous edges ei1 (t, h0 ) (1 ≤ h0 ≤ h − 1) have
chosen the same color as ei1 (t, h). The lemma then follows by noticing that each node picks its color
independently and uniformly at random from Pi .
Lemma 2.3. For all i ∈ [1, L] and t ∈ T , degi1 (t) = ∆(i) with high probability.
n o
Proof. Note that degi1 (t) = min ∆(i) , degi1 (t) . Thus, we only need to prove degi1 (t) ≥ ∆(i) w. h. p. We
do the proof by induction on i. For i = 1, the result directly follows from the definition of early edges and
the fact that the input order is a random permutation. Now, assume the statement is true for i, and we will
prove it for i + 1. Note that for any top node t and any h ≤ ∆(i) , we have by Lemma 2.2:
1 h−1
i
Pr[e1 (t, h) gets accepted] = 1 − (i) .
∆
Therefore
∆(i) (i)
1 h−1 1 ∆
h i
i+1 i (i) (i) (i)
E deg1 (t) deg1 (t) = ∆ = ∆ − ∑ 1 − (i) =∆ 1 − (i)
h=1 ∆ ∆
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 567–595 574
O NLINE G RAPH E DGE -C OLORING IN THE R ANDOM -O RDER A RRIVAL M ODEL
and hence
h i ∆(i)
∆(i) ≥ E degi+1
1 (t) ≥ (1 − o(1)) .
e
A simple application of the method of bounded differences, as in [5], section 6.5.1, shows that degi+1
1 (t)
i+1 (i+1) i+1
is sharply concentrated around its mean. Therefore, w. h. p. deg1 (t) ≥ ∆ , that is deg1 (t) =
∆ (i+1) .
Lemma 2.4. For any i ∈ [1, L], h, (b,t) ∈ E, Pr (b,t) = ei1 (t, h) only depends on i, h (i. e., is independent
of (b,t)).
Proof. We do the proof by induction on i. For i = 1, the statement follows directly from the symmetry of
the input order (random permutation). Now, assume the prove it for i + 1.
claim is true for i, and we will(i+1)
By definition of the algorithm, for any h > ∆(i+1) , Pr (b,t) = ei+1
1 (t, h) = 0. If h ≤ ∆ , we have
0 0
Pr (b,t) = ei+1 i+1 i i
1 (t, h) = ∑ Pr (b,t) = e1 (t, h) | (b,t) = e1 (t, h ) Pr (b,t) = e1 (t, h ) .
h0 ≥h
For each h0 , we know by the inductive that Pr (b,t) = ei1 (t,h0 ) is independent of (b,t).
assumption 0 0
Hence, we only need to show that Pr (b,t) = ei+1 i
1 (t, h) | (b,t) = e1 (t, h ) is only dependent on i, h, h .
Assume that
C = {(c1 , c2 , . . . , ch0 ) | ∀ 1 ≤ j ≤ h0 : c j ∈ Pi ,
the number of different colors among c1 , . . . , ch0 −1 is h0 − h,
and ∃ 1 ≤ j ≤ h0 − 1 : ch0 = c j } .
Then,
h0
0 1
Pr (b,t) = ei+1 i
1 (t, h) | (b,t) = e1 (t, h ) = |C| ,
∆(i)
which clearly only depends on i, h, h0 .
Lemma 2.5. For all i ∈ [1, L] and b ∈ B, degi1 (b) = ∆(i) ± o ∆(i) w. h. p.
Proof. First, notice that from Lemma 2.4, for any (b0 ,t) ∈ E and any h, we have
∆ · Pr (b0 ,t) = ei1 (t, h) = Pr (b00 ,t) = ei1 (t, h) = Pr degi1 (t) ≥ h .
∑
{b00 |(b00 ,t)∈E}
Then, from Lemma 2.3, we have (for any (b0 ,t) ∈ E)
(
1−o(1)
0 if h ≤ ∆(i) ,
Pr (b ,t) = ei1 (t, h) =
∆
0 if h > ∆(i) .
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 567–595 575
BAHMAN BAHMANI , A RANYAK M EHTA , AND R AJEEV M OTWANI
Then, with t being an arbitrary neighbor of b, we have
E degi1 (b) = ∑ Pr (b,t 0 ) reaches phase i = ∆ · Pr [(b,t) reaches phase i]
{t 0 |(b,t 0 )∈E}
∆(i)
= ∆ · ∑ Pr (b,t) = ei1 (t, h) = ∆(i) (1 − o(1)) .
h=1
The sharp concentration proof, using the method of average bounded differences, then exactly follows the
one in [5], section 7.5.3.
Therefore, from Lemma 2.3 and Lemma 2.5, the node degrees drop exponentially quickly, and we get
the following theorem:
S i
Theorem 2.6. With high probability, all round 1 edges get colored from P ∪ P∞ , i. e., the algorithm
does not abort during Round 1.
2.2 Correlations between rejected colors at the end of round 1
In this section, we prove a proposition which will prove very useful later in the analysis of the second
round of the algorithm. First, we give a definition.
Definition 2.7. For i ∈ [1, L], and for a top vertex t, let E i (t) be the set of colors in Pi which were not
used to color a Round 1 edge incident on t. (In other words, it is the set of colors from Pi which no bottom
vertex proposes for a Round 1 edge incident on t.)
Before proceeding to the main proposition, we present the following lemma which is a direct
consequence of the definitions of Ri (b), E i (t) and Lemma 2.3, Lemma 2.5.
Lemma 2.8. For all i ∈ [1, L], b ∈ B, t ∈ T , w. h. p. | Ri (b)| ∼ ∆i+1 and |E i (t)| ∼ ∆(i+1) .
Now, we present the main proposition.
Proposition 2.9. For all i ∈ [1, L], b ∈ B,t ∈ T such that there is no Round 1 edge (b,t), we have w. h. p.
i i 1
R (b) ∩ E (t) ≥ − o(1) Ri (b) .
e
Proof. To simplify the presentation of the proof, assume (b,t) ∈/ E. The proof for the case where (b,t) is
an edge, but not a Round 1 edge, is exactly similar. We first prove that
i i 1
− o(1) E Ri (b) .
E R (b) ∩ E (t) ≥
e
Let the event F i be defined as follows:
n o
F i = ∃b0 ∈ B or t 0 ∈ T : deg1j (b0 ) < ∆( j) − o(∆ j ) or deg1j (t 0 ) < ∆( j) for some 1 ≤ j ≤ i .
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 567–595 576
O NLINE G RAPH E DGE -C OLORING IN THE R ANDOM -O RDER A RRIVAL M ODEL
We know, from Lemma 2.3 and Lemma 2.5, that Pr F i = o(1). Furthermore, we have 0 ≤ Ri (b) ≤ ∆
and hence
h i h i h i
E Ri (b) = E Ri (b) F i Pr F i + E Ri (b) F i Pr F i = o(1) + (1 − o(1)) E Ri (b) F i ,
where F i is the complement of F i . Similarly, one can see
h i
E Ri (b) ∩ E i (t) ≥ (1 − o(1)) E Ri (b) ∩ E i (t)
Fi .
Hence, to prove the inequality in expectation, it suffices to prove that
h i 1 h i
i i
E R (b) ∩ E (t) F ≥ i − o(1) E Ri (b) Fi .
e
Thus, assume F i happens. (I. e., all probabilities and expectations are conditioned on F i . We
will omit
explicitly writing this conditioning for the sake of brevity of expressions.) Then, we have E Ri (b) =
c
∑c∈Pi Pr c ∈ Ri (b) . Denoting by b → z that the algorithm chooses the tentative proposal of c ∈ Pi for
(b, z) and denoting the event n o
c
(b,t 0 ) = ei1 (t 0 , h) and b → t 0
by H i (t 0 , h, c) (for any c ∈ Pi , h ∈ [1, ∆(i) ], (t 0 , b) ∈ E), we have for any c ∈ Pi
Pr c ∈ Ri (b) = ∑ Pr H i (t 0 , h, c) Pr t 0 rejects b H i (t 0 , h, c) .
(2.1)
(b,t 0 )∈E,
1≤h≤∆(i)
Similarly, E Ri (b) ∩ E i (t) = ∑c∈Pi Pr c ∈ Ri (b) ∩ E i (t) and, for any c ∈ Pi ,
Pr c ∈ Ri (b) ∩ E i (t) = ∑ Pr H i (t 0 , h, c) · Pr c ∈ E i (t) H i (t 0 , h, c)
(b,t 0 )∈E
1≤h≤∆(i)
· Pr t 0 rejects b H i (t 0 , h, c), c ∈ E i (t) .
(2.2)
But,
(i)
1 ∆
i i 0
1
Pr c ∈ E (t) H (t , h, c) = 1 − (i) = − o(1)
∆ e
and
Pr t 0 rejects b H i (t 0 , h, c), c ∈ E i (t) ≥ Pr t 0 rejects b | H i (t 0 , h, c) ,
as knowing c ∈ E i (t) increases the chance of c being proposed to t 0 by nodes other than b, which increases
the chance that t 0 rejects b’s proposal of c. Hence, comparing equations (2.1) and (2.2), we get
1
Pr c ∈ Ri (b) ∩ E i (t) ≥ − o(1) Pr c ∈ Ri (b) (∀ c ∈ Pi )
e
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 567–595 577
BAHMAN BAHMANI , A RANYAK M EHTA , AND R AJEEV M OTWANI
and hence
h
h
i i
i 1 i
E R (b) ∩ E (t) Fi ≥ − o(1) E Ri (b) Fi ,
e
which implies that
i i 1
− o(1) E Ri (b) .
E R (b) ∩ E (t) ≥
e
We know | Ri (b)| is sharply concentrated around its mean. The proof for the sharp concentration of
| Ri (b) ∩ E i (t)|, using the method of average bounded differences, also closely follows the proof in [5],
section 7.5.3. Therefore, the inequality also holds with high probability.
Note that, for any i ∈ [1, L], both Ri (b) and E i (t) are random subsets of Pi , with
1 i
Ri (b) ∼ E i (t) ∼ P .
e
The above proposition shows these sets are also w. h. p. positively correlated. This will be important in
our analysis of the second round of the algorithm, presented in the next section.
2.3 Round 2 analysis
Round 2 begins at time rn∆. At this point, we have the following set-up, as proved above: Every bottom
vertex b has, for each i ∈ [1, L], a set Ri (b) ⊆ Pi of colors rejected in Round 1. Every top vertex has, for
each i ∈ [1, L], a set of unused colors E i (t) ⊆ Pi . We proved that w. h. p.
Ri (b) ∩ E i (t) 1
Ri (b) ∼ |E i (t)| ∼ ∆(i+1) and i ≥ .
R (b)| e
For each i ∈ [1, L], we also have the augmenting palette Ni of size xi (to be determined later).
Definition 2.10 (Probabilities pi (t, h), qi (h)). For i ∈ [1, L], define mi = ∆(i+1) + xi to be the total number
of colors that a bottom vertex has in Round 2 to propose for its phase i incident edges (recall that by
Lemma 2.8, ∀ b, | Ri (b)| ∼ ∆(i+1) w. h. p.).
For i ∈ [1, L], t ∈ T , and h ∈ [1, degi2 (t)], and denoting ei2 (t, h) by (b,t), define pi (t, h) to be the
probability that, given that ei2 (t, h) proposes a (randomly chosen) color from Ri (b), this color is in E i (t),
and has not been proposed by any previously arrived edge ei2 (t, h0 ) (h0 < h). In other words pi (t, h) is
the “natural probability” (over the choice of colors proposed for each round 2 edge) of the proposal for
ei2 (t, h) succeeding, given that it chose a color from Ri (b). This probability value can be calculated by the
online algorithm when the edge arrives.
Finally, define
1 h−1
1
qi (h) = 1− .
e mi
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 567–595 578
O NLINE G RAPH E DGE -C OLORING IN THE R ANDOM -O RDER A RRIVAL M ODEL
Figure 4: In this example, each of R1 (b1 ), R1 (b2 ), R1 (b3 ) and R1 (b4 ) are positively correlated to E 1 (t)
(as required by Proposition 2.9). However, R1 (b1 ) = R1 (b2 ) = R1 (b3 ), while R1 (b4 ) ∪ R1 (b1 ) = 0./ The
edge (b4 ,t) has a much greater chance of success than the other three edges. To see this, note that the color
choices of the other three edges may conflict with each other, and hence lead to failure in this palette for
all but one of the conflicting edges. But the color choice of (b4 ,t) would never face a conflict—whenever
the color belongs to E 1 (t), it will be a success. (For simplicity, we have ignored the existence of the new
palette N1 in round 2 in this example.)
Remark 2.11. Note that pi (t, h) depends crucially on which edge (b,t) is in the hth position among the
phase i edges incident on t in Round 2. This is because the edge succeeds in coloring itself if no previous
such edge chose the same color. Since we have no guarantee on how the different Ri (·) sets intersect,
this probability may depend on the identities of all the first h such edges. From this observation, we see
that, unlike in Round 1, different bottom vertices may have very different probabilities of success, even if
their edges were in the same position with respect to a top vertex t. This may result in the degrees of
different vertices evolving differently over the phases, which makes the analysis very difficult. We rectify
this issue by showing that qi (h) is a lower bound on all of these probabilities pi (t, h), and by artificially
rejecting each possible coloring using random coin tosses with appropriate bias (qi (h)/pi (t, h)) to make
the probability of the ith edge succeeding to become exactly qi (h). Note that the values of pi (t, h) are
available to the online algorithm at the time that the edge arrives.
Figure 4 illustrates the reason why some round 2 edges can be luckier than others, based on the
intersection patterns of the sets of available colors at bottom vertices (even though the sets at every pair
of bottom and top vertices are positively correlated).
The following lemma lower bounds all the acceptance probabilities pi (t, h).
Lemma 2.12. pi (t, h) ≥ qi (h).
Proof. Suppose ei2 (t, h) is the edge (b,t). Let newh be the event that the color proposed by ei2 (t, h) from
Ri (b) ∪ Ni is in E i (t) and is not proposed by any of the previous edges ei2 (t, h0 ) (1 ≤ h0 ≤ h − 1). For
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 567–595 579
BAHMAN BAHMANI , A RANYAK M EHTA , AND R AJEEV M OTWANI
h0 ∈ [1, h − 1], let Ri (h0 ) denote the set Ri (b0 ), where ei2 (t, h0 ) has b0 as its bottom vertex. Define
vhc := h0 1 ≤ h0 < h and c ∈ Ri (h0 ) .
We have
pi (t, h) := Pr newh (b,t) gets a proposal from Ri (b)
h i h i
c c
= ∑ Pr newh b → t Pr b → t (b,t) gets a proposal from Ri (b)
c∈Ri (b)
h
1 vc
1
= ∑ 1− i
c∈Ri (b)∩E i (t)
mi R (b)
Ri (b) ∩ E i (t) 1 h−1
≥ 1 −
Ri (b) mi
h−1
1 1
≥ 1− =: qi (h) ,
e mi
where the last inequality uses the positive correlation between Ri (b) and E i (t), from Proposition 2.9.
Definition 2.13. Define
!
1 h−1 ∆(i+1) i 1 h−1 xi 1 ∆(i+1)
xi
succi (h) := 1− + q (h) = 1 − + .
mi mi mi mi mi e mi
Corollary 2.14. The probability that the edge ei2 (t, h) succeeds in coloring itself (in phase i of Round 2)
is exactly succi (h).
Proof. Using the notation of the proof of Lemma 2.12, and defining acch to be the event that ei2 (t, h)
succeeds (i. e., the event of interest), we have:
Pr [acch ] = Pr acch ch ∈ Ni Pr ch ∈ Ni + Pr acch ch ∈ Ri (b) Pr ch ∈ Ri (b) .
But,
Ni ∆i+1 1 h−1
xi
Pr ch ∈ Ni = Pr ch ∈ Ri (b) = i
= , , Pr acch ch ∈ N = 1 − ,
mi mi mi mi
and
Pr acch ch ∈ Ri (b) = Pr acch newh , ch ∈ Ri (b) Pr newh ch ∈ Ri (b)
qi (h) i
= p (t, h) = qi (h) .
pi (t, h)
Putting all these together proves the corollary.
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 567–595 580
O NLINE G RAPH E DGE -C OLORING IN THE R ANDOM -O RDER A RRIVAL M ODEL
Remark 2.15. By using the extra randomness in artificially reducing the probabilities of success for
“lucky” edges, we have decoupled the probability of success from the identities of the vertices, and how
the different Ri (b) sets intersect. Note that all we used was that the Ri (b) and E i (t) sets are positively
correlated (Proposition 2.9)—we made no assumption on how different Ri (b) and Ri (b0 ) intersect. Having
managed this, the rest of the proof is basically identical to the Round 1 analysis.
Definition 2.16. Define the sequence Γi by the following recursion:
r∆
Γ1 = ,
e
Γi 1 2 (i+1)
i+1
Γ = + 1− ∆ .
e e
Choose xi := Γi − ∆(i+1) . Thus, mi = Γi .
Lemma 2.17. For all i ∈ [1, L] and for all nodes v, degi2 (v) ∼ Γi with high probability.
Proof. The proof closely follows the one in round 1. So, we only show the recursion. For an arbitrary top
node t, the expected number of Round 2 edges incident on t which succeed in coloring themselves in
phase i (of Round 2) is
degi2 (t) h−1 !
mi (i+1)
1 x i 1 ∆
E ∑ succi (h) ∼ ∑ 1 − +
h=1 h=1 mi mi e mi
1 (i+1) 1
' xi + ∆ 1−
e e
where the first equality uses Corollary 2.14. Therefore, the number of unsuccessful edges proceeding to
the next phase is
i+1 i 1 (i+1) 1
deg2 ∼ deg2 (t) − xi + ∆ 1−
e e
1 1
∼ Γi − xi + ∆(i+1) 1−
e e
i
2
Γ 1
= + 1− ∆(i+1)
e e
= Γi+1
where the second equation is by the induction hypothesis, the third is because Γi = xi + ∆i+1 by definition
of xi , and the last is by definition of the sequence {Γi }i≥1 .
Corollary 2.18. The algorithm succeeds in coloring all edges w. h. p., i. e., it doesn’t abort in Round 2.
Proof. It can then be easily seen that the recursion for Γi makes all the vertex degrees fall exponentially
quickly (e. g., at a rate at least as large as 1/e + (1 − 1/e)2 ). So, the palette P∞ suffices to greedily color
the edges not colored by Li=1 Pi .
S
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 567–595 581
BAHMAN BAHMANI , A RANYAK M EHTA , AND R AJEEV M OTWANI
2.4 Putting it together
First note that each probabilistic statement claimed in the proof holds w. h. p., i. e., with probability of
error at most 1/ poly(n). We only have poly(n) such statements (2n vertices, 2 rounds and L = O(log n)
palettes per round). So, by a simple union bound, we know that w. h. p. all of those results hold, in which
case the total number of colors that we use is at most
∑ | P i | + ∑ xi + | P ∞ | .
i≥1 i≥1
Now, | Pi | = ∆(i) , and by choice (Definition 2.16), xi = Γi − ∆(i+1) . Thus, the above summation is at most
r∆ + ∑ Γi + o(∆) .
i≥1
By definition,
1 2 r∆
Γi
Γi+1 = + 1 − .
e e ei
Summing up all these equalities (for all i ≥ 1) and defining S = ∑i≥1 Γi , we have
1 2
S r∆
S − Γ1 = + 1 − ∑ ei
e e i≥1
from which we can calculate
1 1
S = r∆ + .
e e−1
Thus, recalling that r = e/(e + 1), we have
1
1 + 1e + e−1
1 1
r∆ + S = r∆ 1 + + = ∆ < 1.43∆ .
e e−1 1 + 1e
Therefore, the total number of colors used is at most 1.43∆ + o(∆). We record this result in the following
theorem.
Theorem 2.19. The online algorithm colors the edges of a regular bipartite graph with degree ∆ =
ω(log n), w. h. p., using at most 1.43∆ + o(∆) colors.
3 Extending the algorithm to more than two rounds
A natural idea is to extend the algorithm to more than two rounds, say to K rounds, so that each color is
tried at each bottom vertex up to K times. This way, we may expect to reduce the total number of colors
used. We define such an algorithm in Figure 5, and describe it informally below.
The algorithm partitions the input edges into K rounds: The first r1 n∆ edges to arrive are called Round
1 edges, the next r2 n∆ edges are Round 2 edges, and so on, where the sequence of numbers r1 , r2 , · · · , rK
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 567–595 582
O NLINE G RAPH E DGE -C OLORING IN THE R ANDOM -O RDER A RRIVAL M ODEL
For all bottom vertices b, all i ∈ [1, L], and all j ∈ [1, K], initialize Triedij (b) = Rij (b) = 0.
/
When the sth edge e = (b,t) arrives in the online order:
j−1 j
• Let j be s.t. ∑`=1 r` < s ≤ ∑`=1 r` (the edge is a Round j edge).
• Set i = 0
• While (e is not colored and i < L):
– i++ S
j−1 i
– Pick a color c∗ uniformly at random from Nij ∪ `=1 R` (b) \ Triedij (b).
Set Triedij (b) = Triedij (b) ∪ {c∗ }. (If no such color exists then continue).
– If no previously arrived edge incident on t was proposed c∗ , then
(a) If c∗ ∈ Nij then color e with c∗
qi
(b) If c∗ ∈ Ri` (b) (for some ` < j) then color e with c∗ with probability pi `,h(t) ,
`,h
and set Ri` (b) = Ri` (b) − c∗ .
– Else: If c∗ ∈ Nij , set Rij (b) = Rij (b) ∪ {c∗ }.
• If e is not yet colored, color it greedily from P∞ . If no such color is available in P∞ , then abort.
Figure 5: The Online Algorithm
will be chosen later. The algorithm keeps L palettes for each round, so that we have a total of KL palettes
Nij , (i ∈ [1, L], j ∈ [1, K]), where the size of each palette will be determined later. The algorithm also has
a special palette P∞ with o(∆) colors.
So, as an edge (b,t) arrives, the arrival time determines which round it belongs to—say it belongs to
round j. Vertex b proposes a random color c for this edge from the union of N1j and the sets of colors
rejected from b in the earlier palettes N11 , . . . , N1j−1 . If t has not used the color c earlier, then the edge
is colored c. Else, b proposes a random color for this edge from the union of N2j and the sets of colors
rejected from b in the earlier palettes N21 , . . . , N2j−1 , and t decides whether or not to accept it, and so on. If
after L such attempts, the edge is still not colored, we will color it greedily from P∞ . Also, as in the 2
round algorithm, we perform some additional artificial rejections of the proposed colors for an edge with
random coin tosses of appropriate biases, so as to keep the success probabilities across all vertices the
same.
In this section, we show how we can analyze the above algorithm. We start with some definitions.
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 567–595 583
BAHMAN BAHMANI , A RANYAK M EHTA , AND R AJEEV M OTWANI
Definition 3.1. The sequence {g` }`≥0 is defined recursively as follows:
g0 = 1 ,
1 2
g`+1 = g` − 1 − g .
e `
Definition 3.2. We say that a round j edge (1 ≤ j ≤ K) reaches phase i (1 ≤ i ≤ L), if it ever proposes a
color from r≤ j Nri . For a vertex v, define degij (v) as the number of round j edges incident on v which
S
reach phase i. For t ∈ T (respectively, b ∈ B), i ∈ [1, L], j ∈ [1, K], and r ≤ j, define Er,i j (t) (respectively,
Air, j (b)) to be the set of colors from Nri which have still not been used to color any edges incident on t
(respectively, b), at the beginning of round j. Thus, Aij, j (b) = N ij , and Air, j (b) equals the value of Rir (b)
(as in the Online Algorithm in Figure 5) at the beginning of round j. For i ∈ [1, L], j ∈ [1, K], t ∈ T and
h ∈ [1, degij (t)], let eij (t, h) be the hth edge incident on t which arrives in round j and reaches phase i.
Suppose eij (t, h) = (b,t), and that b proposes (in the ith phase) the color c for this edge. Then, define
pir, j (t, h) (∀ r ≤ j) as the probability that, given c ∈ Air, j (b), c is also in Er,i j (t), and that no edge eij (t, h0 ),
j
for h0 < h, also proposed c. For i ∈ [1, L], j ∈ [1, K], define d ij = ∑r=1 g j−r |Nri |. Also, with r ≤ j, define
!h−1
1
qir, j (h) := g j−r 1− i .
dj
Finally, define accij (t, h) as the event that eij (t, h) gets colored at phase i (i. e., does not reach phase i + 1).
Now, using the above definitions, we present the following theorem:
Theorem 3.3. For all i ∈ [1, L], j ∈ [1, K], 1 ≤ r ≤ j, b ∈ B, t ∈ T , and h ∈ [1, degij (t)], we have:
1. |Air, j (b)| ∼ |Er,i j | ∼ g j−r |Nri | w. h. p.
2. degij (b) ∼ degij (t) ∼ d ij w. h. p.
3. If there is no edge (b,t) belonging to the rounds earlier than j, then w. h. p. Air, j (b) and Er,i j (t) are
(essentially) positively correlated, i. e., |Air, j (b) ∩ Er,i j (t)| ≥ g j−r |Air, j (b)|.
4. pir, j (t, h) ≥ qir, j (h).
Proof (sketch): The proof is done by induction on the round number j. For j = 1, all the items in the
theorem are trivially true. So, the basis of the induction is fine. The proofs for the inductive step are very
similar to the ones done for the corresponding statements for the 2 Round algorithm. So, we only provide
proof sketches here. We do the inductive proof for the items in the following order: 3, 4, 1, 2.
The proof for item 3 follows exactly the proof of Proposition 2.9. The only difference between Round
1 and any other Round is the artificial rejections done by the random coin tosses. But, clearly, that does
not change the correlation structure between the unused color sets (i. e., Air, j (b) and Er,i j (t)).
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 567–595 584
O NLINE G RAPH E DGE -C OLORING IN THE R ANDOM -O RDER A RRIVAL M ODEL
Then, we prove the item 4. The proof is very similar to that of Lemma 2.12. Suppose eij (t, h) = (b0 ,t).
Let newh be the event that the color proposed for eij (t, h), by b0 in phase i, has not been already used by t,
and that no eij (t, h0 ) chose the same color. Define
( )
0
Air0 , j (h0 )
[
vhc = 1≤h <h c∈
r0 ≤ j
where by Air0 , j (h0 ), we mean the set Air0 , j (b00 ) for bottom node b00 such that eij (t, h0 ) = (b00 ,t). Then,
pir, j (t, h) = Pr newh | eij (t, h) gets a proposal from Air, j (b0 )
h i h i
c c
= ∑ Pr newh | b0 → t · Pr b0 → t | eij (t, h) gets a proposal from Air, j (b0 )
c∈Air, j (b0 )
!vhc
1 1
= ∑T 1− i
c∈Air, j (b0 ) Er,i j (t)
dj |Air, j (b)|
!h−1
|Air, j (b0 ) Er,i j (t)|
T
1
≥ 1− i
|Air, j (b)| dj
!h−1
1
≥ g j−r 1− i = qir, j (h)
dj
where, in the third line, we are using (the inductive assumption for) item 2, and in the inequality in the
last line, we are using item 3.
Next, we prove the item 1. Assume cij (t, h) is the color proposed by eij (t, h) at phase i. Then, we first
show that w. h. p. we have
Pr accij (t, h) | cij (t, h) ∈ Air, j (b0 ) ∼ qir, j (h)
and hence
j
g j−r |Nri | i
Pr accij (t, h) ∼ ∑
qr, j (h) . (3.1)
r=1 d ij
This is because
Pr accij (t, h) | cij (t, h) ∈ Air, j (b0 ) = Pr newh | cij (t, h) ∈ Air, j (b) · Pr accij (t, h) | newh
qir, j (h)
= pir, j (t, h) i = qir, j (h)
pr, j (t, h)
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 567–595 585
BAHMAN BAHMANI , A RANYAK M EHTA , AND R AJEEV M OTWANI
and thus
j
Pr accij (t, h) = ∑ Pr cij (t, h) ∈ Air, j (b) · Pr accij (t, h) | cij (t, h) ∈ Air, j (b)
r=1
j Ai
r, j i
= ∑ i qr, j (h)
r=1 d j
j
g j−r |Nri | i
= ∑ qr, j (h) .
r=1 d ij
Now, let Xr,i j (t) be the number of colors from Er,i j (t) which get used in phase i of round j which get used
to color some edge incident on t. Then,
i
dj
E[Xr,i j (t)] = E ∑ 1cij (t,h)∈Air, j (h), accij (t,h)
h=1
d ij
∑ Pr cij (t, h) ∈ Air, j (h), accij (t, h)
=
h=1
Air, j (h) i
= qr, j (h)
d ij
i !h−1
g j−r |Air, j (h)| d j 1
= ∑ 1− i
d ij h=1 dj
1
= g2j−r |Nri | 1− .
e
Thus, the expected size of Er,i j+1 (t) equals
1
|Er,i j (t)| − E[Xr,i j (t)] ∼ g j−r |Nri | − g2j−r |Nri | 1− = g j+1−r |Nri | .
e
The w. h. p. proof is then standard. Also, a similar calculation, summing over round j edges incident on
node b, gives |Air, j+1 (b)| = g j−r+1 |Nri |. This finishes the proof of item 1.
Finally, for the proof of item 2, notice that equation (3.1) shows that the probability that a round j
edge gets colored at some phase i depends solely on i, j and the position of that edge among the other
round j edges incident on the same top vertex which reach phase i. Note that we get this property in
spite of the fact that the “natural probabilities” of success (namely the pir, j (t, h)’s) depend crucially on
the identities of the first h edges, since they depend on how the various Air, j (b) sets intersect. Using
this property, the proof of item 2, for top vertices, is similar to the above calculations (for item 1) using
equation (3.1), and, for bottom vertices, can be done in almost exactly the same way as in Round 1. So
we omit the details here.
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 567–595 586
O NLINE G RAPH E DGE -C OLORING IN THE R ANDOM -O RDER A RRIVAL M ODEL
3.1 Counting the number of colors used
Theorem 3.3 gives us the essential ingredients for analyzing the multi-round algorithm. So, next, we
proceed to calculating the total number of colors used by the algorithm.
The number of edges (for each vertex) reaching round j of phase i is degij , while the number of old
colors of phase i (from rounds less than j) reaching round j of phase i is equal to the number of edges
(for each vertex) reaching round j − 1 of phase i + 1, i. e., equal to degi+1
j−1 . Therefore, we have:
n o
∀ i ≥ 1, j ≥ 2 : |N ij | = max 0, d ij − d i+1
j−1 . (3.2)
If this number were 0, we would simply not introduce any new colors. However, for the calculation
of the total number of colors (Lemma 3.4), it is easier to drop the max with 0. This may cause us to
undercount the number of colors if the second term in the max was negative.
For now, we assume that in each phase of each round we need to introduce some new colors. That is,
we never have more old colors remaining from the previous rounds than the degree of the nodes in the
current round. Thus our assumption can be stated as:
∀ i ≥ 1, j ≥ 2 : d ij ≥ d i+1
j−1 . (3.3)
From now onwards, we proceed with this assumption and bound the total number of colors used. We will
try to prove the assumption in Section 3.1.1 by reducing it to the question of non-negativity of a certain
sequence of numbers.
Lemma 3.4. The total number of colors used is, w. h. p., ∑K−1 ∞ L i
j=1 r j ∆ + SK + | P |, where SK = ∑i=1 dK .
Proof. From equation (3.2) and Assumption (3.3) we have
|N ij | = d ij − d i+1
j−1 . (3.4)
Hence,
#colors = ∑ |N ij | + | P∞ |
1≤i≤L,1≤ j≤K
K L h i
= ∑ ∑ d ij − d i+1 ∞
j−1 + | P |
j=1 i=1
K−1 L
= ∑ d 1j + ∑ dKi + | P∞ |
j=1 i=1
K−1
= ∑ r j ∆ + SK + | P∞ | .
j=1
where, in the last line, we are using d 1j = r j ∆, which holds because the phase 1 degrees in round j are
equal to r j ∆.
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 567–595 587
BAHMAN BAHMANI , A RANYAK M EHTA , AND R AJEEV M OTWANI
The next step is to bound SK :
Lemma 3.5.
rK ∆
SK ≤ .
1 − 1e gK−1
Proof. From Theorem 3.3, we have for all i ∈ [1, L − 1], j ∈ [1, K]
j
d ij = ∑ g j−r |Nri |
r=1
and from equation (3.4)
j
d i+1
j = d ij+1 − |N ij+1 | = ∑ g j−r+1 |Nri | .
r=1
Hence,
g`+1
d i+1
j ≤ max d ij
0≤`≤ j−1 g`
1
= max 1− 1− g` d ij
0≤l≤ j−1 e
1
= 1− 1− g j−1 d ij .
e
Thus, letting j = K, and doing a simple induction (and recalling dK1 = rK ∆), we have
i−1
i 1
dK ≤ 1 − 1 − gK−1 rK ∆ .
e
Hence,
L
SK = ∑ dKi
i=1
i−1
1
≤ ∑ 1 − 1 − gK−1 rK ∆
i≥1 e
rK ∆
=
1 − 1 − 1 − 1e gK−1
rK ∆
= .
1 − 1e gK−1
From the above lemma, and also noting that ∑Kj=1 r j = 1 and recalling ∆ = ω(log n), the total number
of colors can be bounded as follows:
#colors rK
≤ 1 − rK + + o(1) . (3.5)
1 − 1e gK−1
∆
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 567–595 588
O NLINE G RAPH E DGE -C OLORING IN THE R ANDOM -O RDER A RRIVAL M ODEL
Note that so far we have not yet defined the values for r1 , r2 , . . . , rK , and the above results were independent
of the exact values of these parameters. But now, to get the final bound, we need to determine the values
for these parameters. We do that in the following definition.
Definition 3.6. Define {r j }1≤ j≤K as follows:
1
r1 = ,
∑K−1
j=0 g j
r j = g j−1 r1 (∀ 1 < j ≤ K) .
Notice that these values do satisfy ∑Kj=1 r j = 1.
Using the above definition for {r j }1≤ j≤K , from equation (3.5) we have
#colors r1
≤ 1 − gK−1 r1 + + o(1) . (3.6)
∆ 1 − 1e
Hence, to bound the total number of colors used, we need to bound the sequence {g` }`≥0 . We do so in
the following lemma:
Lemma 3.7. For any ` ≥ 1, we have
1 1
1
≤ g` ≤ .
5 1− e ` 1 − 1e `
Proof. We prove both bounds by induction. We start with proving the upper-bound on g` . For ` = 1, we
have g1 = 1/e ≤ 1/ (1 − 1/e). Now, for the inductive step, assume the upper-bound is true for `; we will
prove it for ` + 1. Since ` ≥ 1, we have g` ≤ 1/e. Also, the function f (x) = x − (1 − 1/e) x2 is monotone
increasing over [0, 1/e]. Hence,
1 2 1 1 1
g`+1 = g` − 1 − g` ≤ 1
− 1− 2
e 1− e ` e 1 − 1e `2
1 1 1 1 `−1 1
= − 2 = 2
≤ 1
.
1 − 1/e ` ` 1 − 1/e ` 1 − e (` + 1)
This finishes the proof for the upper-bound. For the lower bound, we do another induction. For ` = 1,
1 1
g1 = ≥ .
e 5 1 − 1e
For the inductive step, we start with the following obvious inequality:
` 1 1 1 1 1
≥ ⇒ − = ≥ 2.
`+1 5 ` ` + 1 `(` + 1) 5`
Thus,
!2
1 2 1 1 1 1
g`+1 = g` − 1 − g ≥ − 1− ≥
e ` 5 1 − 1e ` 5 1 − 1e ` 1 − 1e
e 5 (` + 1)
which finishes the proof.
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 567–595 589
BAHMAN BAHMANI , A RANYAK M EHTA , AND R AJEEV M OTWANI
Proposition 3.8. If Assumption (3.3) holds, the K-round online algorithm achieves a competitive ratio of
1 + O(1/ log K) + o(1) for any graph with ∆ = ω(log n).
Proof. From Lemma 3.7 and Definition 3.6, we get
1 1
1
≤ r1 ≤
1 + 1 − 1e HK−1
1 + 5 1 − e HK−1
where HK−1 = ∑K−1 st
j=1 1/ j ' ln(K − 1) is the (K − 1) harmonic number. Thus, from equation (3.6), we
see that the competitive ratio of the algorithm with K rounds, converges, as 1 + O(1/ log K) + o(1), to 1
when K increases. Thus, with ∆ = ω(log n), this algorithm achieves, w. h. p., a coloring with ∆ + o(∆)
number of colors (for K large enough, e. g., K = O (log(∆/ log n))).
3.1.1 The non-negativity assumption
This concludes the analysis under the assumption (3.3) that ∀ i ∈ [1, L], j ∈ [1, K], the number of old
colors is not more that the degree at phase i, round j. In this section we attempt to prove this assumption.
We reduce the question to proving the non-negativity of the following sequence of numbers.
Definition 3.9. The sequence {c` }`≥1 is defined recursively as follows:
`−1
c` = g` − ∑ c j g`− j .
j=1
The sequence | Nij | follows a recurrence based on the sequence we just defined.
Lemma 3.10. For any 1 ≤ i < L, 1 ≤ j ≤ K, we have
j
|N i+1 i
j | = ∑ c` |N j−`+1 | .
`=1
Proof. We have degi+1j = ∑`≤ j Nij g j−`+1 , and the number of old colors from phase i + 1, round ` < j
i+1
reaching round j is Nr g j−` . A simple induction leads to the proof of the lemma.
Corollary 3.11. Assuming c` ≥ 0, (∀ ` ∈ [1, K]), with the r j ’s as defined in Definition 3.6, we have
|N ij | ≥ 0 (∀ i ∈ [1, L], j ∈ [1, K]).
Proof. From Definition 3.6, we have: |N11 | = r1 ∆ and |N 1j | = 0 for any 1 < j ≤ K, which shows claim
is true for j = 1. Then, the proof can be completed by a straightforward induction on j. We omit the
details.
This corollary shows that it is sufficient (for non-negativity of all |N ij |’s (i ∈ [1, L], j ∈ [1, K])) to
prove that c` is non-negative for 1 ≤ ` ≤ K. If K is a small constant (e. g., say 3,4,5) , this can be proved
by direct calculation of the values c` up to ` = K. Our computer simulation results, presented in Figure 6,
also show that c` is non-negative up to very large values of K. However, we don’t have a formal proof to
show that all c` ’s (i. e., ∀ ` ≥ 1) are non-negative. However, based on the presented computer simulation
results and our current understanding, we give the following conjecture which we believe to be true.
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 567–595 590
O NLINE G RAPH E DGE -C OLORING IN THE R ANDOM -O RDER A RRIVAL M ODEL
Conjecture 3.12. Defining {g` }`≥0 as in Definition 3.1, and {c` }`≥1 as in Definition 3.9, we have ∀ ` ≥ 1:
c` ≥ 0.
A proof of this conjecture completes the analysis of the near-optimal ∆ + o(∆) coloring. Alternatively,
below we present a simple way to exactly compute the competitive ratio for any K, given we know the
values c` are non-negative for ` up to K.
3.1.2 Computing the number of colors
We show how one can exactly compute the number of colors used by the K-round algorithm, assuming
the non-negativity assumption holds for the first K values of {c` }`≥1 . As proved in Lemma 3.4, the total
number of colors used by the algorithm is, up to lower order terms, (1 − rK )∆ + SK . So, we need to
compute SK = ∑i≥1 dKi . We have, from Theorem 3.3,
K−1
dKi = ∑ g` | Nij−` | .
`=0
Hence,
K−1 K−1
SK = ∑ dKi = ∑ ∑ g` | NiK−` | = ∑ g` ∑ | NiK−` | .
i≥1 i≥1 `=0 `=0 i≥1
Define
A j = ∑ | Nij | .
i≥1
Then, from the recursion in Lemma 3.10, one can easily observe
r1
A1 = ,
1 − 1e
j
Aj = ∑ c j−`+1 A` .
`=1
So, one can first recursively compute A j ’s using the above equation, and then SK can be computed as
K
SK = ∑ gK− j A j
j=1
which then allows computation of the total number of colors used by the K-round algorithm. Using this
method, we can, for instance, compute the exact competitive ratio for the K-round algorithm for small
constants, such as 3,4,5:
Number of Rounds #colors/∆
1 1.6
2 1.43
3 1.35
4 1.30
5 1.26
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 567–595 591
BAHMAN BAHMANI , A RANYAK M EHTA , AND R AJEEV M OTWANI
0
10
ï1
10
ï2
10
ï3
10
ï4
10
ï5
10
ï6
10
ï7
10
0 1 2 3 4
10 10 10 10 10
Figure 6: log log plot of c` vs. `
4 Conclusions and open questions
The following are the three main open questions:
Calculations for the K-round algorithm Prove Conjecture 3.12 or find an alternate way of calculating
the number of colors used in the k-round algorithm.
Analyze the Random algorithm The Random algorithm is possibly the simplest randomized algorithm:
It starts with a palette of a sufficient number of colors. When an edge (b,t) arrives, it is given a random
color from the palette which does not conflict with already arrived neighboring edges on either side. A
variant of this algorithm is studied in [1], proving that, it uses only ∆ + o(∆) colors, when the degree of
the (multi-)graph is ω(n2 ).
One may think of this process as the following propose-accept process (similar to our algorithm):
b picks a random color which has not been used to color previously arrived edges incident on b, and
proposes this color for (b,t). If no edge incident on t has used this color then (b,t) is colored with this
color, else b repeats with a new random choice from the palette, until success. Our algorithm can be
considered a variant of Random which breaks up the palette into several disjoint palettes, and the edges
into K rounds. It allows each color to be tried up to K times at each bottom vertex, once for an edge
from each round. By doing this we manage the correlations between available color sets. The open
question is to analyze the Random algorithm in random or adversarial arrival orders and prove that, with
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 567–595 592
O NLINE G RAPH E DGE -C OLORING IN THE R ANDOM -O RDER A RRIVAL M ODEL
∆ = ω(polylog (n)), a palette of size ∆ + o(∆) suffices.
Adversarial order Find an algorithm with an optimal competitive ratio in the adversarial order.
References
[1] G AGAN AGGARWAL , R AJEEV M OTWANI , D EVAVRAT S HAH , AND A N Z HU: Switch scheduling
via randomized edge coloring. In Proc. 44th FOCS, pp. 502–512. IEEE Comp. Soc. Press, 2003.
[doi:10.1109/SFCS.2003.1238223] 568, 569, 571, 592
[2] A MOTZ BAR -N OY, R AJEEV M OTWANI , AND J OSEPH NAOR: The greedy algorithm is optimal for on-
line edge coloring. Inform. Process. Lett., 44(5):251–253, 1992. [doi:10.1016/0020-0190(92)90209-
E] 569
[3] R ICHARD C OLE , K IRSTIN O ST, AND S TEFAN S CHIRRA: Edge-coloring bipartite multigraphs in
O(E log D) time. Combinatorica, 21(1):5–12, 2001. [doi:10.1007/s004930170002] 568
[4] D EVDATT D UBHASHI , DAVID A. G RABLE , AND A LESSANDRO PANCONESI: Near-optimal, dis-
tributed edge colouring via the nibble method. Theoret. Comput. Sci., 203(2):225–251, 1998.
Preliminary version in ESA’95. [doi:10.1016/S0304-3975(98)00022-X] 571
[5] D EVDATT D UBHASHI AND A LESSANDRO PANCONESI: Concentration of measure for the analysis
of randomized algorithms. Cambridge University Press, New York, NY, USA, 1st edition, 2009. 572,
575, 576, 578
[6] DAVID A. G RABLE AND A LESSANDRO PANCONESI: Nearly optimal distributed edge coloring in
o(log log n) rounds. Random Structures Algorithms, 10(3):385–405, 1997. Preliminary version in
SODA’97. [doi:10.1002/(SICI)1098-2418(199705)10:3<385::AID-RSA6>3.0.CO;2-S] 571
[7] I AN H OLYER: The NP-completeness of edge-coloring. SIAM J. Comput., 10(4):718–720, 1981.
[doi:10.1137/0210055] 568
[8] A LESSANDRO PANCONESI AND A RAVIND S RINIVASAN: Randomized distributed edge coloring via
an extension of the Chernoff-Hoeffding bounds. SIAM J. Comput., 26(2):350–368, 1997. Preliminary
version in PODC’92. [doi:10.1137/S0097539793250767] 568, 571
[9] VADIM G. V IZING: On an estimate of the chromatic class of a p-graph. Metody Diskret. Analiz.,
3:25–30, 1964. 568
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 567–595 593
BAHMAN BAHMANI , A RANYAK M EHTA , AND R AJEEV M OTWANI
AUTHORS
Bahman Bahmani
Ph. D. Student
Stanford University
bahman stanford edu
Aranyak Mehta
Research Scientist
Google Inc., Mountain View, CA
aranyak google com
Rajeev Motwani (1962 - 2009)
Former Professor
Stanford University
rajeev cs stanford edu
ABOUT THE AUTHORS
BAHMAN BAHMANI is a Ph. D. student at Stanford University supported by the William
R. Hewlett Stanford Graduate Fellowship. His research interests are in algorithmic and
architectural aspects of web and large data applications. His Ph. D. advisor was Rajeev
Motwani. After Rajeev’s passing, Ashish Goel and Prabhakar Raghavan became his
advisor and coadvisor. He is a recipient of the Yahoo Key Scientific Challenges Award
for his contributions to the area of search technologies.
A RANYAK M EHTA is a Research Scientist at Google Research, based in Mountain View,
CA. He received his Ph. D. from Georgia Tech in 2005, advised by Dick Lipton and
Vijay Vazirani, with a thesis on algorithmic game theory. He received a B. Tech from
I. I. T. Bombay in 2000, where he started research in theoretical computer science with
the support of Milind Sohoni and Sundar Vishwanathan. His interests lie in online and
approximation algorithms, auction and mechanism design, and in algorithmic and auction
theoretic applications in industry. He grew up in Bombay, inevitably becoming a fan of
cricket and Bollywood, and currently enjoys living in the San Francisco Bay Area.
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 567–595 594
O NLINE G RAPH E DGE -C OLORING IN THE R ANDOM -O RDER A RRIVAL M ODEL
R AJEEV M OTWANI was born on March 24, 1962 in Jammu, India. He died on June 5, 2009.
He received a B. Tech degree in Computer Science from I. I. T. Kanpur in 1983 and a
Ph. D. in Computer Science from University of California at Berkeley in 1988 under
the supervision of Richard Karp. The list of his research interests is long and eclectic,
and includes graph theory, approximation algorithms, randomized algorithms, online
algorithms, complexity theory, web search and information retrieval, databases, data
mining, computational drug design, robotics, streaming algorithms, and data privacy.
He received the Gödel Prize in 2001 for his research on probabilistically checkable
proofs and hardness of approximation. Dr. Motwani successfully spanned both theory
and practice, being an early advisor and supporter of Google, in addition to many other
successful startups and venture firms in Silicon Valley.
T HEORY OF C OMPUTING, Volume 8 (2012), pp. 567–595 595