Graph Edge-Colouring and Minimum Cost Algorithms

In this section the graph edge-colouring and minimum cost problems will be considered. An algorithm which colours the graph with no more than $deg+1$ colours is first given. The problem of minimising the sum of the largest weight of each colour is then considered and an algorithm will be suggested that attempts to solve the problem.

Let $G=(V,E)$ be a graph, where $V$ is the set of vertices and $E$ the set of edges. The degree of a vertex is the number of edges that are linked to the vertex. The degree of a graph, denoted by $deg$, is the maximum degree of all vertices of the graph. Two edges are said to be adjacent if they share the same vertex.

The edge-colouring problem can be defined as follows:

edge-colouring problem    assign each edge of the graph $G$ with a colour, such that no adjacent edges have the same colour.

The chromatic number of a graph, $\chi_1(G)$, is the least number of colours needed to edge-colour the graph. It is easy to see that at least $deg$ colours are needed to colour the graph, so $\chi_1 (G)\ge deg$. In fact an interesting theorem in graph theory, proved by Vizing [15], shows that

Theorem    If $G$ is a graph, then $deg\le\chi_1 (G) \le deg+1$.

Therefore it is always possible to colour the edges of a graph with no more than $deg+1$ colours. However to decide whether it is possible to colour the graph with only $deg$ colours is an NP-complete problem [7]. So a practical bound is $deg+1$ colours.

The proof of the Theorem 1 (see, e.g. [4]) is based on adjusting the colouring of the graph. Let $C$ be the set of $deg+1$ colours. Assume that part of the graph is coloured with colours from $C$. Consider adding an uncoloured edge to the coloured part of the graph. If there is a common unused colour from the colour set $C$ at both ends of the edge, then colour the edge with that colour. Otherwise adjust the colouring of the coloured part of the graph to allow the new edge to be coloured with no conflict.

The following algorithm, which colours a graph $G$ with no more than $deg+1$ colours, is based on the proof of the theorem. Here a path is denoted to be a list of vertices of the form $w_1, w_2, \ldots w_k$, where for $2\le i\le k$, the pair $(w_i, w_{i-1})$ constitutes an edge in $E$ and vertices are not repeated, apart from the case $w_1=w_k$.

Algorithm COLOUR

• step 1    Let $C$ be the set of $deg+1$ colours. Let $G^C$ be the part of the graph whose edges were coloured using colours in $C$ with no conflict.
• step 2    Find an edge $e=(v,w)\in G$ that is not in $G^C$, where $v$ and $w$ are two ends of the edge $e$. If no such edge exists then all the edges have been coloured with colours in $C$, so terminate.
• step 3    If there is a colour $c\in C$ unused at both ends $v$ and $w$, then colour the edge $e=(v,w)$ with the colour $c$, add the edge and both ends to $G^C$, go to step 2. Otherwise let $c_1\in C$ be an unused colour at $v$ and $c_2\in C$ be an unused colour at $w$.
• step 4    Starting from $w$, find the largest path in $G^C$ coloured with colours $c_1$ and $c_2$ alternately. Let the path be $w, w_1, w_2, \ldots ,w_k$.
• step 5    If $w_k\ne v$ then exchange the colours $c_1$ and $c_2$ in the path, colour the edge $e=(v,w)$ with $c_1$, add the edge and its ends to $G^C$, go to step 2.
• step 6    Otherwise, if there is a colour $c_3$ unused both at $v$ and $w_{k-1}$ then change the colour of the edge $(v,w_{k-1})$ from $c_2$ to $c_3$. Colour the edge $e=(v,w)$ with $c_2$, add $e$ and its ends to $G^C$, go to step 2.
• step 7    Else let $c_3$ be an unused colour at $w_{k-1}$. Uncolour the edge $(v,w_{k-1})$ and delete it and its ends from $G^C$. Colour the edge $e=(v,w)$ with colour $c_2$ and add it and its ends to $G^C$. Rename $w_{k-1}$ as $w$, $c_3$ as $c_2$, the edge $(v,w_{k-1})$ as $e$ and repeat the procedure from step 4.

In practice there is usually more than one colouring scheme that edge-colours the graph with no more than $deg+1$ colours. Let $S$ be the set of all such colouring schemes. The cost of each colouring scheme, is defined as the sum of the largest weight of the edges that have the same colour. For example, in Figure 3 (a), edges (1,6), (2,5) and (3,4) have colour $c_1$, with a largest weight of $\max\{4,1,6\}=6$; edges (1,2) and (6,5) have colour $c_2$, with the largest weight of $\max\{6,1\}=6$; edges (2,3) and (5,4) have colour $c_3$, with the largest weight of $\max\{1,5\}=5$, thus the cost of the colouring scheme given by Figure 3 (a) is $6+6+5=17.$ The minimum cost problem can be stated as following

minimum cost problem    Among all colouring scheme $s\in S$, find one that has the minimum cost.

Although the algorithm COLOUR can give a colouring scheme with no more than $deg+1$ colours, the colouring scheme may not be the one with minimum cost. To illustrate this, Table 3 presents a communication task table given by partitioning a mesh of 788 elements into 16 subdomains, using a spectral bisection algorithm. Thus the graph described by the table has 16 vertices. The maximum degree is $deg=5.$ Applying algorithm COLOUR on the graph of Table 3 results in the scheduling scheme given by Table 4. In this case 5 colours are used. If one views the table as a communication schedule, then in the 5-th stage, processor 10 exchanges messages with processor 13, which needs 10 units of time. Processors 11 and 12 exchange messages which need 2 units of time, the rest of the processors are idle. A better balancing of the communication load at each stage will reduce the overall communication costs.

Table 3: A communication task table resulting from partitioning a mesh of 788 elements into 16 subdomains

Processor	$adjproc\ (msglen)$
1	9 (2)	12 (2)	-	-	-
2	3 (3)	10 (1)	11 (3)	13 (6)	-
3	2 (3)	10 (4)	11 (8)	12 (1)	-
4	7 (3)	14 (5)	15 (6)	-	-
5	9 (2)	10 (4)	-	-	-
6	11 (4)	12 (5)	16 (4)	-	-
7	4 (3)	10 (2)	13 (4)	14 (6)	-
8	15 (6)	16 (6)	-	-	-
9	1 (2)	5 (2)	-	-	-
10	2 (1)	3 (4)	5 (4)	7 (2)	13 (10)
11	2 (3)	3 (8)	6 (4)	12 (2)	-
12	1 (2)	3 (1)	6 (5)	11 (2)	16 (6)
13	2 (6)	7 (4)	10 (10)	14 (3)	-
14	4 (5)	7 (6)	13 (3)	-	-
15	4 (6)	8 (6)	-	-	-
16	6 (4)	8 (6)	12 (6)	-	-

Table 4: A scheduling scheme for the task given in Table 3

Processor	$adjproc\ (msglen)$
1	9 ( 2)	12 ( 2)	-	-	-
2	3 ( 3)	10 ( 1)	11 ( 3)	13 ( 6)	-
3	2 ( 3)	11 ( 8)	10 ( 4)	12 ( 1)	-
4	7 ( 3)	14 ( 5)	15 ( 6)	-	-
5	10 ( 4)	9 ( 2)	-	-	-
6	11 ( 4)	16 ( 4)	12 ( 5)	-	-
7	4 ( 3)	13 ( 4)	14 ( 6)	10 ( 2)	-
8	15 ( 6)	-	16 ( 6)	-	-
9	1 ( 2)	5 ( 2)	-	-	-
10	5 ( 4)	2 ( 1)	3 ( 4)	7 ( 2)	13 ( 10)
11	6 ( 4)	3 ( 8)	2 ( 3)	-	12 ( 2)
12	16 ( 6)	1 ( 2)	6 ( 5)	3 ( 1)	11 ( 2)
13	14 ( 3)	7 ( 4)	-	2 ( 6)	10 ( 10)
14	13 ( 3)	4 ( 5)	7 ( 6)	-	-
15	8 ( 6)	-	4 ( 6)	-	-
16	12 ( 6)	6 ( 4)	8 ( 6)	-	-
max. $msglen$	6	8	6	6	10
comm. cost	36

The following algorithm is proposed in an attempt to solve the minimum cost problem. The idea is to colour as many as possible the edges with large weights using one colour, then repeat the procedure recursively for the remaining edges.

The algorithm, named REDUCE, starts with a graph edge-colouring with no more than $deg+1$ colours. Roughly speaking, a) first the edge $e_1$ with the largest weight is found and locked, its colour is $c_1$; b) Then the unlocked edge $e_2$ with the largest weight is found, its colour is $c_2$. An attempt is then made to colour the two edges $e_1$ and $e_2$ with the same colour; c) If $c_1=c_2$, then the two edges with largest weights have indeed the same colour, so lock $e_2$. Otherwise the following steps are carried out to change the colour of $e_2$ into $c_1$; d) If at both ends of the edge $e_2$, colour $c_1$ is unused, then the colour of $e_2$ can simply be changed to $c_1$. Otherwise the logic used in the algorithm COLOUR can be adapted; e) The largest path containing the edge $e_2$ and coloured alternately with $c_1$ and $c_2$ is found. If it contains locked edges, then lock $e_2$; otherwise the two colours on the path are exchanged making $e_2$ having the same colour as $e_1$, and lock $e_2$. This process is repeated from b) until all edges are locked. The edges with colour $c_1$ are then removed and the process repeated on the remaining graph. In this way edges with similar weights are coloured with the same colour. The detailed algorithm is as follows, where

$c(e)=$ the colour of edge $e$,

$E(G)=$ the set of edges of a graph $G$,

$E_L=$ the set of locked edges,

$E_U=$ the set of unlocked edges.

The algorithm starts with the graph $G$, and first colours it with the algorithm COLOUR.

Algorithm REDUCE

• step 1    Edge-colour the graph G with algorithm COLOUR.
• step 2    Let $E_L=\emptyset$, $E_U=E(G)$.
• step 3    If $E_U=\emptyset$ then terminate. Otherwise let $e_1$ be the edge in $E_U$ with the largest weight, let $c_1=c(e_1)$, $E_L=E_L\cup\{e_1\}$, $E_U=E_U\setminus\{e_1\}$.
• step 4    If $E_U=\emptyset$ go to step 7. Otherwise let $e_2$ be the edge in $E_U$ with the largest weight, let $c_2=c(e_2)$.
• step 5    If $c_2=c_1$ then $E_L=E_L\cup\{e_2\}$, $E_U=E_U \setminus\{e_2\}$, go to step 4.
• step 6    Find the largest path that contains $e_2$ and is coloured with $c_1$ and $c_2$ alternately. If the path contains locked edges, then let $E_L=E_L\cup\{e_2\}$, $E_U=E_U \setminus\{e_2\}$, go to step 4. Otherwise exchange the colours $c_1$ and $c_2$ on the path, let $E_L=E_L\cup\{e_2\}$, $E_U=E_U \setminus\{e_2\}$, go to step 4.
• step 7    Remove the edges with colour $c_1$ from the graph. Rename the remaining graph as $G$, go to step 2.

This algorithm is a descent algorithm, in the sense that given a colouring scheme of a graph, applying REDUCE will always produce a colouring scheme with a cost not more than that of the original scheme. This is proved in the following theorem.

Theorem      The algorithm REDUCE applied to an edge-coloured graph results in a colouring scheme with the cost not more than that of the original colouring scheme.

Proof     In the algorithm, the only place where the colouring scheme might be modified is at step 6, when a path with non-locked edges, coloured with $c_1$ and $c_2$ alternately, is found and the two colours are exchanged. On this path, and in fact among all unlocked edges, $e_2$ is the edge with the largest weight. When the colour $c_1$ and $c_2$ are exchanged, the cost for colour $c_1$ remains equal to the weight of $e_1$, because this is the edge with the largest weight among all the edges in the current graph. The cost for colour $c_2$ will not increase because those edges that changed their colours from $c_1$ to $c_2$ have weights smaller than that of the edge $e_2$, as $e_2$ is the edge in $E_U$ with the largest weight. Therefore overall, the cost of the new colour scheme will not be more than that of the original colouring scheme

In the actual implementation of the algorithm, if the cost is reduced, then the algorithm is restarted on the new coloured graph. This process is repeated until no further reduction is possible.

Figure 4: Applying algorithm REDUCE to a communication task graph: (a) Communication cost$=6+6+5=17$; (b) $e_1=(3,4)$, $e_2=(1,2)$, path $=1,\ 2,\ 5,\ 6.$ Exchange colours $c_1$ and $c_2$ on the path. Lock $e_1$ and $e_2$; (c) No more improvement possible. Remove colour $c_1;$ (d) $e_1=(5,4)$, $e_2=(1,6)$, change colour of $e_2$ to $c_3$. Lock $e_1$ and $e_2;$ (e) No more reduction possible, final scheme with communication cost $=6+1+5=12.$

An example is given by the graph in Figure 3 (a). The process of applying REDUCE to the graph is shown in Figure 4. As a further example, applying the algorithm to the scheduling scheme of Table 4 gives the scheduling scheme of Table 5, the cost is reduced from 36 to 26 - a significant saving.

Table 5: A scheme for the task given in Table 3, with reduced communication cost compared with Table 4

Processor	$adjproc\ (msglen)$
1	12 ( 2)	-	-	-	9 ( 2)
2	3 ( 3)	11 ( 3)	10 ( 1)	13 ( 6)	-
3	2 ( 3)	12 ( 1)	-	10 ( 4)	11 ( 8)
4	-	-	7 ( 3)	14 ( 5)	15 ( 6)
5	10 ( 4)	-	-	9 ( 2)	-
6	16 ( 4)	-	-	11 ( 4)	12 ( 5)
7	13 ( 4)	10 ( 2)	4 ( 3)	-	14 ( 6)
8	-	-	-	15 ( 6)	16 ( 6)
9	-	-	-	5 ( 2)	1 ( 2)
10	5 ( 4)	7 ( 2)	2 ( 1)	3 ( 4)	13 ( 10)
11	-	2 ( 3)	12 ( 2)	6 ( 4)	3 ( 8)
12	1 ( 2)	3 ( 1)	11 ( 2)	16 ( 6)	6 ( 5)
13	7 ( 4)	14 ( 3)	-	2 ( 6)	10 ( 10)
14	-	13 ( 3)	-	4 ( 5)	7 ( 6)
15	-	-	-	8 ( 6)	4 ( 6)
16	6 ( 4)	-	-	12 ( 6)	8 ( 6)
max. $msglen$	4	3	3	6	10
comm. cost	26

When the algorithm REDUCE terminates, it is not necessary that a global minimum has been found. For that reason we will also test an algorithm which takes the best result for ten runs of the algorithm REDUCE, each run starts with randomly permuted edge and vertex indices. This algorithm is denoted as REDUCE10.

The three algorithms are applied to the communication task graphs resulting from partitioning five meshes of various sizes (given in the column ``mesh'' of the table) using a spectral bisection algorithm. The number of colours and the cost of the colouring scheme generated by the three algorithms are given in Table 6.

Table 6: Comparison of three edge-colouring algorithms by the ``number of colours/cost'', on the communication task graphs resulting from the partitioning of five meshes using a recursive spectral bisection algorithm. Here $p$ is the number of sudomains

$p$	mesh	COLOUR	REDUCE	REDUCE10
16	771	6/44	6/34	6/30
16	788	5/36	5/26	5/25
16	3564	6/74	6/59	5/56
16	5520	5/385	4/216	4/216
32	353710	17/4678	17/2042	17/2028
64	353710	28/4140	28/1853	28/1823
128	353710	36/3433	36/1214	36/1196
256	353710	37/2715	37/930	37/902

From Table 6 it is clear that both the algorithms REDUCE and REDUCE10 improve significantly the cost of the colouring scheme given by the algorithm COLOUR.

Hosted by www.Geocities.ws