Distributed Computing, COMP 4001 1
Distributed
Graph Coloring
, , SCS (September 11, 2021)
Distributed Computing, COMP 4001 2
Outline
• Coloring the Plane
• Introduction
• Distributed Computation
– Input (Garbage) Collection
– Coloring
• Non-Distributed Algorithms
• Distributed Algorithms
• Algorithms on Trees
, , SCS (September 11, 2021)
Distributed Computing, COMP 4001 3
Coloring the Plane
, , SCS (September 11, 2021)
Distributed Computing, COMP 4001 4
An Open Problem
• Color the plane R2 without any restrictions and by assigning a
single color to every point of the plane.
– Given a positive integer n, we say that the plane is
n-colored, if every point of the plane is assigned one of the
given n colors.
• Problem 1 What is the smallest number of colors su�cient
for coloring the Euclidean plane in such a way that no two
points of the same color are unit distance apart?
– This number is called the chromatic number of the plane
and is denoted by �(R2).a
aSoifer, Alexander. The mathematical coloring book: Mathematics of color-
ing and the colorful life of its creators. Springer Science, 2008.
, , SCS (September 11, 2021)
•
• •
%
i.try
in square
triangle
tiling –
Distributed Computing, COMP 4001 5
Proof of �(R2) � 3
• Here is the proof.
• Assume on the contrary two colors su�ce.
• Draw an equilateral “unit” triangle anywhere on the plane.
• Since the triangle has three vertices, two vertices must have the
same color, which is a contradiction.
• Surprisingly all we know is that
4 �(R2) 7
• See Exercises 2 and 3 for a proof of 4 �(R2) and �(R2) 9.
, , SCS (September 11, 2021)
• B
n ^
Boo n • a
hexagonal
tiling
→
Distributed Computing, COMP 4001 6
Introduction
, , SCS (September 11, 2021)
Distributed Computing, COMP 4001 7
Vertex Coloring
• What is the min number of “vertex colors” needed in a graph
so that any two neighoring nodes have di↵erent colors?
• An important problem in graph theory…and
– even more so in Distributed Computing.
• It is also a useful way to introduce basic concepts in distributed
computing.
• Has quite a few practical applications,
– In wireless networks where it is the basis of so-called TDMA
MAC protocols.
– In distributed computing, vertex coloring is also used to
break symmetries.
• We investigate the problem in an abstract setting.
, , SCS (September 11, 2021)
①
→
Distributed Computing, COMP 4001 8
But . . . Where is the Novelty?
• We compare three approaches:
1. Centralized
2. Parallel
3. Distributed
• Which approach is the most e�cient?
, , SCS (September 11, 2021)
Distributed Computing, COMP 4001 9
Di↵erent Fields Di↵erent Approaches (Coloring)
• Centralized algorithms
– Graph G is encoded as a string, and the string is given as
input to a computer.
– The computer program finds a coloring of the graph,
encodes the coloring as a string, and outputs the result.
• Parallel algorithms
– Graph G is encoded as a string. However, multiple
computers can access the same string in parallel.
– Each computer might focus on one part of the graph and
produce a coloring for that part.
– Main focus is on high-performance computation exploiting
the processing power of multiple computers in parallel.
, , SCS (September 11, 2021)
{
mm
Distributed Computing, COMP 4001 10
Di↵erent Fields Di↵erent Approaches (Coloring)
• Distributed algorithms
– Graph G is the structure of the computer network.
– There is one computer for each node of G and one
communication link for each edge of G.
– Initially, each computer only knows about its immediate
neighbors in the graph G; the computers must exchange
messages with each other to discover more about the
structure of G.
– Each computer must produce its own color as output.
– The main focus is on coordinating the operation of an
arbitrary distributed system.
• So there are di↵erent approaches
, , SCS (September 11, 2021)
Distributed Computing, COMP 4001 11
Similarities and Di↵erent Approaches (Coloring)
• Parallel algorithms have a di↵erent focus than distributed
algorithms,
– there is a lot of interaction between the two fields.
– sometimes same technique can also be used directly as a
distributed algorithm.
• A parallel algorithm can be implemented either in a parallel
system (using shared memory) or in a distributed system
(using message passing).
• The traditional boundary between parallel and distributed
algorithms (choose a suitable network vs. run in any given
network) does not lie in the same place as the boundary
between parallel and distributed systems (shared memory vs.
message passing).
, , SCS (September 11, 2021)
Distributed Computing, COMP 4001 12
Holding an Election: Input Collection
• You are given as input graph.
• Each node in the graph voted YES or NO after holding an
election and recorded its vote at the node.
• If I am a(ny) node in the graph can I decide whether or not
there is a YES somewhere in a node (possibly another one) of
the graph?
, , SCS (September 11, 2021)
Yes =Blank
•f§° Mo = Red
Distributed Computing, COMP 4001 13
What is a Distributed Computation?
• Can I solve the problem with a
– centralized computation?
– distributed computation?
– mobile agent?
– random walk?
• How do I ensure that every node gets the correct outcome?
• How do these computations di↵er?
, , SCS (September 11, 2021)
0 ☐
Drunkard
✓
✓
=
Distributed Computing, COMP 4001 14
Example coloring:
• How many colours do you need?
• Can be a challenge even in a centralized setting!
, , SCS (September 11, 2021)
1
206 %oa?
‘
☐ ☐
3
joy
3 1
¥,
”
Distributed Computing, COMP 4001 15
Vertex Coloring Problem
• Vertex Coloring.
Given an undirected graph G = (V,E), assign a color �(u) to
each vertex u 2 V such that for any edge e = {v, w} 2 E we
have that u, v are assigned di↵erent colors, i.e., �(v) 6= �(w).
• Example.
• Usually, we denote the colors with positive integers.
• The chromatic number of G, denoted by �(G), is the smallest
number k for which G is k-colourable.
, , SCS (September 11, 2021)
✗pupa
chrome
0
Distributed Computing, COMP 4001 16
Example:
• How many colours do you need?
• �(G) for the Petersen graph is 3.
, , SCS (September 11, 2021)
Distributed Computing, COMP 4001 17
Examples
• Determine �(G) for the graphs below:
• K7
, , SCS (September 11, 2021)
I 2 1 2
② a • 21 3 ”
l z
1
2
Distributed Computing, COMP 4001 18
How Many Colors Do You Need?
• If a graph G has n vertices, then �(G) n.
– However, this upper bound is usually poor, except when G
has many edges.
– This inequality becomes an equality �(G) = n only when G
is the complete graph Kn.
• We can improve on this upper bound considerably if we know
the largest vertex degree in G.
, , SCS (September 11, 2021)
✗camo aÉ¥¥o÷É
Distributed Computing, COMP 4001 19
How Many Colors Do You Need?
• Theorem 1 Let G be a simple graph whose maximum vertex
degree is d. Then �(G) d+ 1.
• Proof: By induction on n.
• Step 1: True for n = 1 (graph has one node and d = 0).
• Step 2: Assume �(H) d+ 1 for all simple graphs H with
fewer than n vertices.
– We wish to show that �(G) d+ 1 for all simple graphs G
with exactly n vertices.
, , SCS (September 11, 2021)
Distributed Computing, COMP 4001 20
How Many Colors Do You Need?
• Let G be a simple graph with n vertices and maximum vertex
degree d.
• Let H be any graph obtained from G by removing a vertex v
and all the edges incident with it.
• The graph H has fewer than n vertices and maximum vertex
degree d (or less) so, by our assumption, �(H) d+ 1, that is,
the graph H is (d+ 1)-colourable.
, , SCS (September 11, 2021)
d¥÷÷÷÷””
–
: i. .
0
I cancolor v with
one ofthe
colors 1,2, ydt
1?
→← E. be
¥÷¥¥÷¥÷÷-*
÷
Distributed Computing, COMP 4001 21
How Many Colors Do You Need?
• We can now obtain a (d+ 1)-colouring of G by colouring v with
any colour not assigned to the (at most d) vertices adjacent to
v, since these vertices can be coloured with at most d colours.
– Here we used the fact that the max degree is d.
• It follows that �(G) d+ 1.
• Thus if the statement is true for all simple graphs with fewer
than n vertices, then it is true for all simple graphs with n
vertices. This completes Step 2.
• Therefore, by the principle of mathematical induction, the
statement is true for all simple graphs with n vertices, for each
positive integer n.
, , SCS (September 11, 2021)
Distributed Computing, COMP 4001 22
As an Algorithm
• Can you present the previous method as an algorithm?
– It has to be based on selecting a vertex and removing it.
– Which vertex will be removed?
• Is the decision of “removing” centralized or distributed?
– If centralized, it is clear who will make the decision!
– Not so clear if distributed since more than one node may
decide to be removed!
• Example. What happens if both nodes 1 and 2 decide to be
removed?
, , SCS (September 11, 2021)
Distributed Computing, COMP 4001 23
Example (1/4)
• How many colours do you need with centralized computation?
• A central algorithm decides on the colors.
, , SCS (September 11, 2021)
0 I
Distributed Computing, COMP 4001 24
Example (2/4)
• How many colours do you need with distributed computation?
• A distributed algorithm decides on the colors.
– Di↵erent nodes may start at the same time!
– How are messages exchanged?
, , SCS (September 11, 2021)
Distributed Computing, COMP 4001 25
Example (3/4)
• How many colours do you need with distributed computation?
• A distributed algorithm decides on the colors.
– Di↵erent nodes may start at the same time!
– What happens when a vertex receives “conflicting signals”.
– What color should it use?
, , SCS (September 11, 2021)
Distributed Computing, COMP 4001 26
Example (4/4)
• Imagine a mobile agent doing a random walk (jumping from
vertex to vertex) colouring vertices?
– Can it decide colorability?
• How can a mobile agent do it?
, , SCS (September 11, 2021)
Distributed Computing, COMP 4001 27
Node Identifiers
• We assume that we have node identifiers.
• Each node has a unique identifier, e.g., its IP address.
• We usually assume that each identifier consists of only O(log n)
bits if the network has n nodes.
• Sometimes we might even assume that the nodes have exactly
the identifiers 1, . . . , n.
, , SCS (September 11, 2021)
@
• Vertices
• Ports
11 a • Node Identifiers
2 31
•
a
5
• Port Identifies
2
Distributed Computing, COMP 4001 28
Node Identifiers
• The size of the identifiers (in bits) may impact the complexity
of an algorithm.
– Identifiers are (may be) exchanged during the distributed
computation.
• How do you assign unique identifiers to the nodes with
distributed computation?
• Previously we discussed a randomized algorithm for assigning
identifiers.
• NB: Identifiers should not be confused with port numbers!
, , SCS (September 11, 2021)
}
Distributed Computing, COMP 4001 29
Chromatic Number
• Node identifiers provide a solution to the coloring problem
– they are pairwise di↵erent;
– essentially requiring n colors.
• Chromatic Number.
Given an undirected Graph G = (V,E), the chromatic number
�(G) is the minimum number of colors to solve the graph
colouring problem for G.
• Basic Questions.
– How many colors are needed is a well-studied problem, but
in the centralized model!
– How many colors are needed in distributed computation
model?
• The type of computation a↵ects the chromatic number!
, , SCS (September 11, 2021)
Distributed Computing, COMP 4001 30
Non-Distributed
Algorithms
, , SCS (September 11, 2021)
Distributed Computing, COMP 4001 31
Non-distributed Vertex Coloring Algorithm
• Without loss of generality we may assume colors are numbers.
• Algorithm: Greedy Sequential
• Input Graph G
1. while there exists an uncolored vertex v do
2. color v with the minimal color (number) that does not
conflict with the already colored neighbors
3. end while
, , SCS (September 11, 2021)
§
put vertices in sequence
a
, big d) e , . . – –
Distributed Computing, COMP 4001 32
Example:
• How do we color this graph?
• Use colors 1, 2, 3, 4, . . .
• Start at a node and use the algorithm.
, , SCS (September 11, 2021)
ok In a distributed
.
⑤⑧ setting, a
sequential
algorithm⑧⑧
will not¥0
always work .
Distributed Computing, COMP 4001 33
Example: Other Graphs
• How do we color these graphs?
, , SCS (September 11, 2021)
Distributed Computing, COMP 4001 34
Issues
• Who starts the coloring?
– The vertex with smallest identifier!
– The algorithm then proceeds in order of identifiers!
• This is a sequential algorithm:
– Only one processor is active at a time!
– This is kind of cheating!
, , SCS (September 11, 2021)
Distributed Computing, COMP 4001 35
Issues
• Nodes are assumed to have distinct identifiers.
• At least, can we show the algorithm is good?
• But according to what benchmark?
– By that we usually mean, how does it perform with respect
to the global (centralized) algorithm?
• E.g., Is the number of colors of Centralized and Distributed
algorithms the same?
, , SCS (September 11, 2021)
Distributed Computing, COMP 4001 36
Degree of a Graph
• (Degree). The number of neighbors of a vertex v, denoted by
�(v), is called the degree of v.
• ( ). The maximum degree vertex in a graph G
defines the graph degree �(G) = � (also denoted d := d(G)).
, , SCS (September 11, 2021)
Distributed Computing, COMP 4001 37
Better Way to State the Algorithm
• Start with a graph G and a list of available colours, say
1, 2, 3, . . .
• Label the vertices a, b, c, . . . in any manner.
– Identify the uncoloured vertex labelled with the earliest
letter in the alphabet;
– colour it with the first colour in the list not used for any
adjacent coloured vertex.
• Repeat Step 2 of the algorithm until all the vertices are
coloured, then Stop.
, , SCS (September 11, 2021)
Distributed Computing, COMP 4001 38
Example (1/2)
• Find a vertex colouring of the following graph G
• Label the vertices a, . . . , f as follows.
, , SCS (September 11, 2021)
asbs . – –
2. (?) Use “Moser’s Spindle”
to show that �(R2) � 4.b
aNot to hand in!
bFor additional research see: Soifer, Alexander. The mathematical coloring
book: Mathematics of coloring and the colorful life of its creators. Springer
Science, 2008.
, , SCS (September 11, 2021)
Distributed Computing, COMP 4001 69
3. (?) Use the following tiling of the plane
to show that �(R2) 9.
4. Show that in any graph the sum of the degrees of all the
vertices is equal to twice the number of edges.
5. Determine the chromatic number �(G) of the graphs below:
For each graph, devise a suitable colouring and explain why
there is no colouring with fewer colours.
, , SCS (September 11, 2021)
Distributed Computing, COMP 4001 70
6. What can you say about the graphs G for which (a) �(G) = 1?
(b) �(G) = 2?
7. In a connected graph, what is the smallest number of edges
that must be removed in order that no cycles remain?
8. What is chromatic number of the graph below
9. A forest with k (connected) components and n vertices has
n� k edges.
10. How many edges does a cycle graph (denoted by Cn) with n
vertices have? What is the diameter of Cn? What is the degree
, , SCS (September 11, 2021)
Distributed Computing, COMP 4001 71
sequence of Cn?
11. A wheel graph with n vertices, denoted by Wn, is obtained
from a cycle graph Cn with n vertices by adding a new vertex
w and joining an edge from w to each vertex of Cn. How many
vertices does Wn have? How many edges does Wn have? What
is the diameter of Wn? What is the degree sequence of Wn?
12. Are any of the following two pairs of graphs isomorphic? If so,
find a suitable one-one correspondence between the vertices of
the first and those of the second; if not, explain why no such
one-one correspondence exists.
If necessary, you can show this by drawing the correspondence.
, , SCS (September 11, 2021)
Distributed Computing, COMP 4001 72
13. The degree sequence of a graph is the sequence of vertex
degrees in non-decreasing order (with repetitions). Prove or
disprove the statements below.
(a) If two graphs are isomorphic, must they have the same
degree sequence?
(b) If two graphs have the same degree sequence, must they be
isomorphic?
14. Assume that 25 chicks sit on vertices of a square 5⇥ 5 grid
(one chick per vertex). Suddenly, each chick randomly pecks a
neighboring chick selected randomly and independently with
equal probability. What is the expected number of unpecked
chicks?
15. Prove that adding an edge to a graph increases its chromatic
number by at most one.
16. Prove that deleting a vertex from a graph decreases the
, , SCS (September 11, 2021)
Distributed Computing, COMP 4001 73
chromatic number by at most one.
, , SCS (September 11, 2021)