Discrete Applied Mathematics 131 (2003) 179 – 198
www.elsevier.com/locate/dam

Graph coloring on coarse grained
multicomputers!
Assefaw Hadish Gebremedhina , Isabelle Gu!erin Lassousb ,Jens Gustedtc , Jan Arne Tellea
a Department of Informatics, University of Bergen, 5020 Bergen, Norwayb INRIA Rocquencourt, Francec LORIA and INRIA Lorraine, France

Received 24 August 2000; received in revised form 16 November 2001; accepted 5 May 2002

Abstract
We present an e"cient and scalable coarse grained multicomputer (CGM) coloring algorithm
that colors a graph G with at most ! + 1 colors where ! is the maximum degree in G. Thisalgorithm is given in two variants: randomized and deterministic. We show that on a p-processor
CGM model the proposed algorithms require a parallel time of O(|G|=p) and a total work andoverall communication cost of O(|G|). These bounds correspond to the average case for the
randomized version and to the worst case for the deterministic variant.
? 2003 Elsevier B.V. All rights reserved.
Keywords: Graph algorithms; Parallel algorithms; Graph coloring; Coarse grained multicomputers

1. Introduction
The graph coloring problem deals with the assignment of positive integers (colors)
to the vertices of a graph such that adjacent vertices do not get the same color andthe number of colors used is minimized. A wide range of real-world problems, among
others, time tabling and scheduling frequency assignment, register allocation, and ef#cient estimation of sparse matrices in optimization, have successfully been modeled! Research supported in part by The Aurora Programme, a France-Norway Collaboration Research Projectof The Research Council of Norway, The French Ministry of Foreign A$airs and The Ministry of Education,
Research and Technology.
E-mail addresses: assefaw@ii.uib.no (A.H. Gebremedhin), isabelle.guerin-lassous@inria.fr (I. Lassous),
jens.gustedt@loria.fr (J. Gustedt), telle@ii.uib.no (J.A. Telle).
0166-218X/03/$ - see front matter ? 2003 Elsevier B.V. All rights reserved.
PII: S 0 1 6 6 - 2 1 8 X ( 0 2 ) 0 0 4 2 4 - 9

180

A.H. Gebremedhin et al. / Discrete Applied Mathematics 131 (2003) 179 – 198

using the graph coloring problem. See [2,4,8,20] for some of the works in each ofthese applications, respectively. Besides modeling real-world problems, graph coloring
plays a crucial role in the #eld of parallel computation. In particular, when a computational task is modeled using a graph where the vertices represent the subtasks and theedges correspond to the relationship among them, graph coloring is used in dividing
the subtasks into independent sets that can be performed concurrently.
The graph coloring problem is known to be NP-hard [9], making heuristic approaches
inevitable in practice. There exist a number of sequential graph coloring heuristics thatare quite e$ective in coloring graphs encountered in practical applications. See [4] forsome of the popular heuristics. However, due to their inherent sequential nature, theseheuristics are di"cult to parallelize. In fact, in [12], coloring the vertices of a graphin a given order where each vertex is assigned the smallest color that has not been
given to any of its neighbors is shown to be P-complete. Consequently, parallel graphcoloring heuristics of di$erent %avor than the e$ective sequential coloring heuristics
had to be suggested. One of the important contributions in this regard is the parallel
maximal-independent set #nding algorithm of Luby [21] and the coloring algorithm
based on it. Subsequently, Jones and Plassmann [16] improved Luby’s algorithm andin addition used graph partitioning as a means to achieve a distributed memory coloringheuristic based on explicit message-passing. Unfortunately, Jones and Plassmann did not
get any speedup from their experimental studies. Later, Allwright et al. [1] performed acomparative study of the implementations of the Jones–Plassmann algorithm and a few
other variations and reported that none of the algorithms included in the study yielded
any speedup. The justi#cation for the usage of these parallel coloring heuristics has
been the fact that they enabled solving large-scale problems that could not otherwise#t onto the memory of a sequential machine.
Despite these discouraging experiences, Gebremedhin and Manne [10] recently proposed a shared memory parallel coloring algorithm that yields good speedup. Theirtheoretical analysis using the PRAM model shows that the algorithm is expected toprovide an almost linear speedup and experimental results conducted on the Origin
2000 supercomputer using graphs that arise from #nite element methods and eigenvalue computations validate the theoretical analysis.
The purpose of this paper is to make this successful approach feasible for a larger
variety of architectures by extending it to the coarse grained multicomputer (CGM)
model of parallel computation [6]. The CGM model makes an abstraction of the interconnection network among the processors of a parallel computer (or network ofcomputers) and captures the e"ciency of a parallel algorithm using only a few parameters. Several experiments show that the CGM model is of practical relevance:
implementations of algorithms formulated in the CGM model in general, turn out tobe portable, predictable, and e"cient [13,14].
In this paper, we propose a CGM coloring algorithm that colors a graph G withat most ! + 1 colors where ! is the maximum degree in G. The algorithm is given
in two variants: one randomized and the other deterministic. We show that the proposed algorithms require a parallel time of O(|G|=p) and a total work and overall
communication cost of O(|G|). These bounds correspond to the average case for the
randomized version and to the worst case for the deterministic variant.

A.H. Gebremedhin et al. / Discrete Applied Mathematics 131 (2003) 179 – 198

181

The remainder of this paper is organized as follows. In Section 2 we review the
CGM model of parallel computation and the graph coloring problem. In Section 3 wediscuss a good data organization for our CGM algorithms and present the randomized
variant of the algorithm along with its various subroutines. In Section 4 we provide
an average case analysis of the randomized algorithm’s time and work complexity.
In Section 5 we show how to de-randomize our algorithm to achieve the same goodtime and work complexity also in the worst case. Finally, in Section 6 we give someconcluding remarks.
2. Background2.1. Coarse grained models of parallel computation
In the last decade, several e$orts have been made to de#ne models of parallel (ordistributed) computation that are more realistic than the classical PRAM models; see[7] or [19] for an overview of PRAM models. In contrast to the PRAM models that
suppose that the number of processors p is polynomial in the input size N , the newmodels are coarse grained, i.e. they assume that p and N are orders of magnitude
apart. Due to this assumption, the coarse grained models map much better on existingarchitectures where, in general, the number of processors is in the order of hundreds
and the size of the data to be handled could be in the order of billions.
The introduction of bulk synchronous parallel (BSP) bridging model for parallel
computation by Valiant [24] marked the beginning of the increasing research interest incoarse grained parallel computation. The BSP model was later modi#ed along di$erent
directions. For example, Culler et al. [5] suggested the LogP model as an extension of
Valiant’s BSP model in which asynchronous execution was modeled and a parameter
was added to better account for communication overhead. In an e$ort to de#ne aparallel computation model that retains the advantages of coarse grained models whileat the same time is simple to use (involves few parameters), Dehne et al. [6] suggested
the CGM model.
The CGM model considered in this paper is well suited for the design of algorithms
that are not too dependent on a particular architecture and our basic assumptions of
the model are listed below.
• The model consists of p processors and all the processors have the same size M =O(N=p) of memory, where N is the input size.
• An algorithm on this model proceeds in the so-called supersteps. A superstep consistsof one phase of local computation and one phase of interprocessor communication.
• The communication network between the processors can be arbitrary.
The goal when designing an algorithm in this model is to keep the sum total of thecomputational cost per processor, the overall communication cost, and idle time ofeach processor within T=s(p), where T is the runtime of the best sequential algorithm
on the same input, and the speedup s(p) is a function that should be as close to p as
possible.

182

A.H. Gebremedhin et al. / Discrete Applied Mathematics 131 (2003) 179 – 198

To achieve this, it is desirable to keep the number of supersteps of such an algorithm
as low as possible, preferably within o(M ). The rationale here lies in the fact that,among others, the message startup-cost and the bandwidth of an architecture determine
the communication overhead. In each superstep, a processor may need to do at mostO(p) communications and hence a number of supersteps of o(M ) ensures that the total
startup-cost is at most O(Mp) = O(N ) and therefore lies within the complexity boundof the overall computational cost we anticipate for such an algorithm. The bandwidth
restriction of a speci#c platform must still be observed, and here the best strategy is
to reduce the communication volume as much as possible. See [13] for an overview
of algorithms, implementations and experiments on the CGM model.
As a legacy from the PRAM model, it is usually assumed that the number of supersteps should be polylogarithmic in p. However, the assumption seems to have nopractical justi#cation. In fact, there is no known relationship between the coarse grainedmodels and the complexity classes NC k . In practice, algorithms that simply ensure
number of supersteps that are functions of p (but not of N ) perform quite well [11].
To be able to organize the supersteps well, we assume that each processor can store
a vector of size p for every other processor. Thus, the following inequality is assumed
throughout this paper:p2 ¡ M:(1)

2.2. Graph coloring
A graph coloring is a labeling of the vertices of a graph G = (V; E) with positive
integers, called colors, such that adjacent vertices do not obtain the same color. It canequivalently be viewed as searching for a partition of the vertex set of the graph into
independent sets. The primary objective in the graph coloring problem is to minimize
the number of colors used. Even though coloring a graph with the fewest number ofcolors is an NP-hard problem, in many applications coloring using a bounded numberof colors, possibly far from the minimum, may su"ce. Particularly, in many parallelgraph algorithms, a bounded coloring (partition into independent sets) is needed asa subroutine. For example, graph coloring is used in the development of a parallel
algorithm for computing the eigenvalues of certain matrices [22] and in parallel partial
di$erential equation solvers [1].
One of the simplest and yet quite e$ective sequential heuristics for graph coloringis the greedy algorithm that visits the vertices of the graph in some order and in each
visit assigns a vertex the smallest color that has not been used by any of the vertex’s
neighbors. It is easy to see that, for a graph G = (V; E), such a greedy algorithm
always uses at most ! + 1 colors, where ! = maxv∈V {degree of v}. In Greenlaw et al.
[12], a restricted variant of the greedy algorithm in which the ordering of the vertices
is prede#ned, and the algorithm is required to respect the given order, is termed as
Lexicographically First ! + 1-coloring (LF! + 1-coloring). We refer to the case where
this restriction is absent and where the only requirement is that the resulting coloringuses at most ! + 1 colors, simply as ! + 1-coloring.

A.H. Gebremedhin et al. / Discrete Applied Mathematics 131 (2003) 179 – 198

183

The LF! + 1-coloring is known to be P-complete [12]. But for special classes ofgraphs, some NC algorithms have been developed for it. For example, Chelbus et al.
[3] show that for tree structured graphs LF! + 1-coloring is in NC. In the absence ofthe lexicographically #rst requirement, a few NC algorithms for general graphs havebeen proposed. Luby [21] has given an NC algorithm for ! + 1-coloring by reducing
the coloring problem to the maximal independent set problem. Moreover, Karchmer
and Naor [17], Karlo$ [18], and Hajnal Szemer!edi [15] have each presented di$erent
NC algorithms for Brook’s coloring (a coloring that uses at most ! colors for a graphwhose chromatic number is bounded by !). Earlier, Naor [23] had established thatcoloring planar graphs using #ve colors is in NC.
However, all of these NC coloring algorithms are mainly of theoretical interest as
they require polynomial number of processors, whereas, in reality, one has only a limited number of processors on a given parallel computer. In this regard, Gebremedhinand Manne [10] have recently shown a practical and e$ective shared memory parallel! + 1-coloring algorithm. They show that distributing the vertices of a graph evenly
among the available processors and coloring the vertices on each processor concurrently, while checking for color compatibility with already colored neighbors, createsvery few con%icts. More speci#cally, the probability that a pair of adjacent vertices
are colored at exactly the same instance of the computation is quite small. On a somewhat simpli#ed level, the algorithm of Gebremedhin and Manne works by tackling thelist of vertices numbered from 1 to n in a ‘round robin’ manner. At a given time t,where 1 6 t 6 r and r = !n=p", processor Pi colors vertex (i − 1)r + t. The sharedmemory assumptions ensure that Pi may access the color information of any vertex
at unit cost of time. Adjacent vertices that are, in fact, handled at exactly the sametime are the only causes for concern as they may result in con%icts. Gebremedhinand Manne show that the number of such con%icts is small on expectation, and that
con%icts can easily be resolved a posteriori. Their analysis of the resulting algorithm
using the PRAM model shows that the algorithm colors a general graph G = (V; E)
with ! + 1 colors in! an expected time O(|G|=p), when the number of processors p issuch that p 6 |V |= 2|E|.
However, in a distributed memory setting, the most common case in our target model
CGM, one has to be more careful about access to data located on other processors.
3. A CGM ! + 1-coloring algorithm
We start this section by discussing how we distribute the input graph among theavailable processors for our CGM ! + 1-coloring algorithms. Then, the randomized
variant of our algorithm is presented in a top-down fashion, starting with an overview
and #lling the details as the presentation proceeds.
3.1. Data distribution
In general, a good data organization is crucial for the e"ciency of a distributed
memory parallel algorithm. For our CGM-coloring algorithm in particular, the input

184

A.H. Gebremedhin et al. / Discrete Applied Mathematics 131 (2003) 179 – 198

graph G = (V; E) is organized in the following manner:• Each"p processor Pi (1 6 i 6 p) is responsible for a subset Ui of the vertices (V =i=1 Ui ). With a slight abuse of notation, the processor hosting a vertex v is denotedby Pv .
• Each edge e = {v; w} ∈ E is represented as arcs (v; w) stored at Pv , and (w; v) stored
at Pw .
• For each arc (v; w) processor Pv stores the identity of Pw and thus the location of
the arc (w; v). This is to avoid a logarithmic blow-up due to the search for Pw .
• The arcs are sorted lexicographically and stored as a linked list per vertex.
In this data distribution, we require that the degree of each vertex be less than D =!N=p", where N = |E|. Vertices with degree greater than D are treated in a separate
preprocessing step.
If the input of the algorithm is not of the desired form, it can be e"ciently transformed into one by carrying out the following steps.
• Generate two arcs for each edge as described above,• Radix sort (see [13] for a CGM radix sort) the list of arcs such that each processor
receives the arc (v; w) if it is responsible for vertex w,• Let every processor note its identity on these sibling arcs,• Radix sort the list of arcs such that every processor receives its proper arcs (arcs(v; w) if it is responsible for vertex v).
3.2. The algorithm (Schemes 1–9)
As the time complexity of sequential ! + 1-coloring is linear in the size of the graph|G|, our aim is to design a parallel algorithm in CGM with O(|G|=p) work per processor
and O(|G|) overall communication cost. In an overview, our CGM coloring algorithm
consists of two phases, an initial and a main recursive phase; see Algorithm 1.

In the initial phase, the subgraph induced by the vertices with degree greater than
!N=p" is colored sequentially on one of the processors. Clearly, there are at most p
such vertices since otherwise we would have more than N edges in total. Thus, thesubgraph induced by these vertices has at most p2 edges. Since p2 is assumed to beless than M , the induced subgraph #ts on a single processor (say P1 ) and a call to
Algorithm 3 colors it sequentially. Algorithm 3 is also used in another situation thancoloring such vertices. We defer the discussion on the details of Algorithm 3 to Section
3.2.1 where the situation that calls for its second use is presented.

A.H. Gebremedhin et al. / Discrete Applied Mathematics 131 (2003) 179 – 198

185

Fig. 1. Graph on 72 vertices distributed onto 6 processors and 4 timeslots.

The main part of Algorithm 1 is the call to Algorithm 2 which recursively colors
any graph G such that the maximum degree ! 6 M . The basic idea of the algorithm
is based on placing the vertices residing on each processor into di$erent timeslots.
The assignment of timeslots to the vertices gives rise to two categories of edges. The#rst category consists of edges which connect vertices having the same timeslot. We
call these edges bad and all other edges good. Fig. 1 shows an example of a graphdistributed on 6 processors and 4 timeslots in which the bad edges are shown in bold.
In a nutshell, Algorithm 2 proceeds timeslot-by-timeslot where in each timeslot thegraph de#ned by the bad edges and the vertices incident on them is identi#ed andthe algorithm is called recursively with the identi#ed graph as input while the rest of
the input graph is colored concurrently.
In Algorithm 2, while partitioning the vertices into k timeslots, where 1 ¡ k 6 p, we
would like to achieve as even a distribution as possible. The call to Algorithm 6 in line
group vertices does this by using the degree of each vertex as a criterion. This randomized algorithm is presented in Section 3.2.2.2 where the issue of load balancing is brie%ydiscussed. Prior to calling Algorithm 6, vertices with ‘high degrees’ that would otherwise result in an uneven load balance are treated separately; see line high degree. The
algorithm for treating high degree vertices, Algorithm 5, is presented in Section 3.2.2.1.
Notice that an attempt to concurrently color vertices incident on a bad edge may
result in an inconsistent coloring (con%ict). In a similar situation, Gebremedhin andManne, in their shared memory formulation, tentatively allow such con%icts and resolve
eventual con%icts in a later sequential phase. The success of their approach lies in thefact that the expected size of the edges in con%ict is relatively small. In our case, wedeal with the potential con%icts a priori. We #rst identify the subgraphs that could
result in con%ict and then color these subgraphs in parallel recursively until their unionis small enough to #t onto the memory of a single processor. See lines identify con!icts
and recurse in Algorithm 2. Note that, in general, some processors may receive morevertices than others. We must ensure that these recursive calls do not produce a blow-up
in computation and communication. In order to ensure that the subgraph that goes into

186

A.H. Gebremedhin et al. / Discrete Applied Mathematics 131 (2003) 179 – 198

recursion is evenly distributed among the processors, a call to Algorithm 7 is made atline balance load. Algorithm 7 is discussed in Section 3.2.2.3.
In the recursive calls one must handle the restrictions that are imposed by previously
colored vertices. We extend the problem speci#cation and assume that a vertex v also
has a list Fv of forbidden colors that initially is empty. An important issue for thecomplexity bounds is that a forbidden color is added to Fv only when the knowledge
about it arrives on Pv . The list Fv as a whole will only be touched once, namely whenv is #nally colored.
Observe also that the recursive calls in line resolve need not be synchronized. In otherwords, it is not necessary (nor desired) that the processors start recursion at exactly
the same moment in time. During recursion, when the calls reach the communication
phase of the algorithm, they will automatically be synchronized in waiting for datafrom each other.

A.H. Gebremedhin et al. / Discrete Applied Mathematics 131 (2003) 179 – 198

187

Clearly, the subgraph de#ned by the good edges and their incident vertices can becolored concurrently by the available processors. In particular, each processor is responsible for coloring its set of vertices as shown in line color vertex of Algorithm
2. In determining the least available color to a vertex, each processor maintains a
Boolean vector Bcolors. This vector is indexed with the colors and initialized withall values set to ‘true’. Then when processing a vertex v, the entries of Bcolors
corresponding to v’s list of forbidden colors are set to ‘false’. After that, the #rst
item in Bcolors that is still true is looked for and chosen as the color of v. Then,the vector is reset by assigning all its modi#ed values the value ‘true’ for futureuse.
After a processor has colored a vertex, it communicates the color information toprocessors hosting a neighbor. In each timeslot the messages to the other processors
are grouped together, see send messages and receive messages. This way at most p − 1
messages are sent per processor per timeslot.

188

A.H. Gebremedhin et al. / Discrete Applied Mathematics 131 (2003) 179 – 198

3.2.1. The base case
The base case of the recursion is handled by a call to Algorithm 3 (see base case in
Algorithm 2). Note that the sizes of the lists Fv of forbidden colors that the vertices
might have collected during higher levels of recursion may actually be too large andtheir union might not #t on a single processor. To handle this situation properly, we
proceed in three steps as shown in Algorithm 3. Notice that Algorithm 3 is the sameroutine called in the initial phase of Algorithm 1.
In the step "nd allowed, for each vertex v ∈ V " a short list of allowed colors Av is
computed. Observe that a vertex v can always be colored using one color from the set{1; 2; : : : ; d(v) + 1}, where d(v) is the degree of v. Hence, a list of d(v) + 1 allowed
colors su"ces to take all restrictions of forbidden colors into account. Using a similar
technique as described in color vertex of Algorithm 2, we can obtain a sorted list Avof allowed colors for v in time proportional to |Fv | + d(v). This is done by the call to
Algorithm 4 in line "nd allowed. Then in the step color sequentially, the vertices of
the input graph are colored sequentially using their computed lists of allowed colors.
In the #nal step communicate, the color information of the vertices is communicated.
3.2.2. Load balancing
In this section, we address the issue of load balancing. In Algorithm 2, three mattersthat potentially result in an uneven load balance are: (i) high variation in the degrees ofthe vertices, (ii) high variation in the sum of the degrees in the timeslots, and (iii) theA.H. Gebremedhin et al. / Discrete Applied Mathematics 131 (2003) 179 – 198

189

recursive calls on the subgraphs that go into recursion. The following three paragraphs
are concerned with these points.
3.2.2.1. Handling high degree vertices. Whereas for the shared memory algorithm
di$erences in degrees of the vertices that are colored in parallel just causes a slightasynchrony in the execution of the algorithm, in a CGM setting it might result in asevere load imbalance and even in memory over%ow of a processor.
Line group vertices of Algorithm 2 groups the vertices into k 6 p timeslots of about
equal degree sum. If the variation in the degrees of the vertices is too large, such agrouping would not be even. For example, if we have one vertex of very large degree,
it would always dominate the degree sum of its time slot thereby creating an imbalance.
So, we have to make sure that the degree of each vertex is fairly small, namely smaller
than !M " =q" where q is a parameter of Algorithm 5. Observe that the notion of ‘small’degree depends on the input size M " and thus may change during the course of thealgorithm. This is why we need to have the line high degree in every recursive call andnot only at the top level call. Note that q is a multiple of k, the number of timeslotsof Algorithm 2.
Thus, the high degree vertices that we indeed have to treat in each recursive call arethose vertices v with !M " =q" ¡ deg(v) 6 M " . Such vertices are handled using Algorithm 5, which essentially divides the set of high degree vertices into k " 6 q timeslots
and colors each of the subgraphs induced by these timeslots sequentially.
3.2.2.2. Grouping vertices into timeslots. Algorithm 6 partitions the vertices into ktimeslots. It does so by #rst dividing the set of vertices into groups of size k andthen distributing the vertices of each group into the distinct timeslots. Observe that nocommunication is required during the course of this algorithm.
The partition obtained with this algorithm is relatively balanced.
Lemma 1. On each processor P, the di!erence of the degree sums of the vertices inany two timeslots is at most the maximum degree over all vertices that P holds.
Proof. Since the vertices are considered in descending order of their degrees, the difference in degree sums between two timeslots is maximized when one of the timeslots
always receives the vertex with the highest degree in the group and the other the smallest. In group i, the vertex of highest degree is vik+1 and the one of smallest degree isv(i+1)k . Thus, we can estimate the di$erence as follows:#s=k$−1#s=k$−1#s=k$−1#s=k$−2

i=0

i=0

i=0

i=0

#

deg(vik+1 ) −#deg(v(i+1)k ) ≤#deg(vik+1 ) −#deg(v(i+1)k+1 );which is in turn bounded by deg(v1 ), where v1 has the maximum degree over all
vertices that P holds.
From Lemma 1 and from the fact that we do not have high degree vertices, itfollows that the sum of the degrees of the vertices in any timeslot is between M " =2k

190

A.H. Gebremedhin et al. / Discrete Applied Mathematics 131 (2003) 179 – 198

and 3M " =2k.

3.2.2.3. Balancing during recursion. In Algorithm 2, unless proper attention is paid,
the edges of the subgraph that goes into recursion may not be evenly distributed among
the processors. To address this, we suggest an algorithm that ensures that Grec , the graphthat goes into recursion in Algorithm 2, is evenly distributed among the processors.
See Algorithm 7.

Obviously Algorithm 7 runs in time proportional to the input size on each processor
and has a constant number of supersteps.
4. Average case analysis
In this section we provide an average case analysis of Algorithm 2. In Section 5 weshow how to replace the randomized algorithm, Algorithm 6, by a deterministic one.
All the lemmas in this section refer to Algorithm 2 unless stated otherwise.
Lemma 2. For any edge {v; w}, the probability that tv = tw is at most 1=k.

A.H. Gebremedhin et al. / Discrete Applied Mathematics 131 (2003) 179 – 198

191

Proof. Consider Algorithm 6. We distinguish between two cases. The #rst is the casewhere v and w reside on di$erent processors. In this case, the choices for the timeslotsof v and w are clearly independent, implying that the probability that w is in the sametimeslot as v is 1=k.
The same argument applies for the case where v and w reside on the same processor
but are not processed in the same group. Whenever they are in the same group, they
are never placed into the same timeslot. Therefore, the overall probability is boundedby 1=k.
Lemma 3. The expected sum total of the number of edges of all subgraphs going
into recursion in recurse is at most |E " |=k.
Proof. The expected total number of edges going into recursion
is equal to the expected$
total number of bad edges. The latter is in turn equal to e∈E ! prob(e is bad), which
by Lemma 2 can be bounded by |E " |=k.
Lemma 4. The expected overall size of the subgraphs at the ith recursion level is at
most N=k i , with at most M=k i per processor.
Proof. Notice that the choices of timeslots between two successive recursion levels
may not be independent. However, the dependency that may occur actually reduces
the number of bad edges even more. This can be seen from a similar argument as thatof Lemma 2: vertices that are in the same group of the degree sequence in Algorithm
6 are forced to be separated into two di$erent timeslots. For all others, the choices areagain independent.
Thus, the total number of edges going into recursion can be immediately boundedby N=k i . The fact that it is also balanced across the processors is due to Algorithm
7.
Lemma 5. The expected sum total of the sizes of all the subgraphs handled by any
processor during Algorithm 2 (including all recursions) is O(M ).
Proof. By Lemma 4, the expected sum of the sizes of these graphs is bounded by∞#i=0

k −i M =k
M 6 2Mk −1(2)

for all k ¿ 2. Thus, the total expected size in all the steps per processor is O(M ).
Lemma 6. For any 1 ¡ k 6 p, the expected number of supersteps is at most quadratic
in p.
Proof. The expected recursion depth of our algorithm is the minimum value d suchthat N=k d 6 M = N=p, which implies k d ¿ p, i.e. d = !logk p". The total number ofsupersteps in each call (including the supersteps in Algorithm 5) is c · k, for some192

A.H. Gebremedhin et al. / Discrete Applied Mathematics 131 (2003) 179 – 198

constant c ¿ 1. The constant c captures the following supersteps:• some to handle high degree vertices,• one to propagate the chosen timeslots,• some to balance the edges inside each timeslot,• one to propagate the colors for each timeslot.
Thus, the total number of supersteps on recursion level i is c · k i and the expected
number of supersteps is bounded as follows:#logk p$#i=1

c · k i 6 c · k logk p+1 = c · k · p:(3)

Lemma 7. The expected overall work involved in base case is O(M ).
Proof. Algorithm 3 on input G " = (V " ; E " ) and lists of forbidden colors Fv has overall
work and communication cost proportional to |G " | and the size of the lists Fv .
There are k #logk p$ expected calls to Algorithm 3 in Algorithm 2; therefore P1 is expected to handle k #logk p$ N=kp2 edges and k #logk p$ N=kp2 6 k 1+logk p N=kp2 6 kpN=kp2 =M . This implies an expected work and communication cost of O(M ) for base case.
Lemma 8. The expected overall work per processor involved in high degree is O(M ).
Proof. In Algorithm 2, in the #rst call to Algorithm 5 (M " = M ), every processor
holds at most q = 2k high degree vertices (i.e vertices v of degree degv (G) such that
N=pq ¡ degv (G) 6 N=p). Otherwise, it would hold more than (M=q) · q = M edges. So,
overall, there are at most p · q such vertices for the #rst level of recursion. Processor
P1 distributes these O(p2 ) vertices onto k " timeslots such that each timeslot has adegree sum of at most 2N=p = 2M . Thus, each timeslot induces a graph of expected
size 2M=k " . Subsequently, sequential ! + 1-coloring is called for the subgraph inducedby each timeslot, for total work O(M ) = O(M " ).
By induction we see that in the ith level of recursion, if a vertex v is of high degree,
its degree degv (Grec ) has to be M " =q ¡ degv (Grec ) 6 M " . Using the same argument as
the one above, it can be shown that the total work to handle these vertices is O(M " ).
From Lemma 5, the total expected work in all the steps per processor is O(M ).
Lemma 9. The expected overall work per processor involved in group vertices isO(M ).
Proof. Observe that the radix sort can be done in O(M " ), since the sort keys are lessthan M " . The random permutations can easily be computed locally in linear time.
Again, Lemma 5 proves the claim.
Theorem 1. For any 1 ¡ k 6 p, the expected work, communication, and idle time perprocessor of Algorithm 2 is within O(M ). In particular, the expected total run-time
per processor is O(M ).

A.H. Gebremedhin et al. / Discrete Applied Mathematics 131 (2003) 179 – 198

193

Proof. From Lemma 6 we see that the expected number of supersteps is O(p2 ); hence
by inequality (1) the expected communication overhead generated in all the superstepsis O(M ).
We proceed by showing that the work and communication that a processor has toperform in Algorithm 2 is a function of the number of edges on that processor, i.e.
M . Inserting a new forbidden color into an unsorted list Fv can be done in constanttime. Since an edge contributes an item to the list of forbidden colors of one of its
incident vertices at most once, the size of such a list is bounded by the degree of thevertex. Thus, the total size of these lists on any of the processors will never exceed
the input size M " (recall that vertices of degree greater than N=p have been handled
in the preprocessing step).
As discussed in Section 3.2, a Boolean vector Bcolors is used in determining thecolor to be assigned to a vertex. In the absence of high degree vertices no list Fv will
be longer than M " =q and hence the size of Bcolors need not exceed M " =q + 1. Even
when this restriction is relaxed, as shown in Section 3.2.2.1, we need at most p colors
for vertices of degree greater than N=p and need not add more than !" + 1 colors,
where !" is the maximum degree among the remaining vertices (!" 6 M " ). Overall,this means that we have at most p + M " + 1 colors and hence the vector Bcolors still#ts on a single processor. So, Bcolors can be initialized in a preprocessing step in timeO(M " ).
After that, coloring any vertex v can be done in time proportional to the size of Av ,which is bounded by the degree of v. Thus, the overall time spent per processor incoloring vertices is O(M " ). By Lemma 5, the expected total time (including recursions)per processor is O(M ).
Lemmas 7–9 show that the contributions of base case, high degree, and recurse in
Algorithm 2 are within O(M ) per processor, proving the claim on the total amount ofwork per processor.
As for processor idle time, observe that the bottleneck in all the algorithms aspresented is the sequential processing of parts of the graphs by processor 1. Since thetotal run time (of Algorithm 3) on processor 1 is expected to be O(M ), the same
expected bound holds for the idle time of the other processors.
5. An add-on to achieve a good worst case behavior
So far, for a possible implementation of our algorithm, we have some degree of
freedom in choosing the number of timeslots k. If our goal is just to get results
based on expected values as shown in Section 4, we can avoid recursion by choosingk = p and by replacing the recursive call in Algorithm 2 by a call to Sequential! +1Coloring(Grec ; {Fv }v ) (Algorithm 3). We can do this since by Lemma 4 the expected
size of Grec is N=k, which in this case means N=p = M , implying that Grec #ts on one
processor. The resulting algorithm would have cp supersteps, for some integer c ¿ 1;
see Lemma 6.
To get a deterministic algorithm with a good worst case bound, we choose the otherextreme, namely k = 2, and replace the call to the randomized Algorithm 6, in line

194

A.H. Gebremedhin et al. / Discrete Applied Mathematics 131 (2003) 179 – 198

group vertices of Algorithm 2, by a call to Algorithms 8 and 9. This will enable us
to bound the number of edges that go into recursion, i.e. the bad edges. We need to
distinguish between two types of edges: internal and external edges. Internal edges
have both of their endpoints on the same processor while external edges have theirendpoints on di$erent processors.
First we argue that internal edges are handled by the call to Algorithm 8, and later
we will argue that external edges are handled by the subsequent call to Algorithm 9.
For internal edges, the following two points need to be observed:(1) The vertices are grouped into two timeslots of about equal degree sum.
(2) Most of the internal edges are good.
To achieve the #rst goal, Algorithm 8 #rst calls Algorithm 5 to get rid of vertices with
degree ¿ M=8. The constant 8 is somewhat arbitrary and could be replaced by any
constant k " ¿ 2 depending on the needs of an implementation. Algorithm 8 groups thevertices of internal edges according to (1) and (2) above into bucket[0] and bucket[1]that will form the two timeslots. A bucket is said to be full when the degree sum of
its vertices becomes greater than M=2.
Proposition 1. Suppose "i M of the edges on processor Pi are external (0 6 "i M 6 M ).
Then after an application of Algorithm 8, at least ( 14 − "i =2)M of the edges on Pi
are good internal edges and each bucket has a degree sum of at most 5M=8.
Proof. Considering the fact that each vertex is of degree less than M=8, the claim forthe degree sum is immediate.
To see the lower bound on the number of good internal edges, consider the bucket
B that became full. The vertices in B have a degree sum of at least M=2 and at least( 12 − "i )M of these edges are internal. We claim that at least half of these internaledges are good.

For the following argument, suppose that an edge is considered only when its second
endpoint is placed into a bucket. We distinguish between two types of internal edges.

A.H. Gebremedhin et al. / Discrete Applied Mathematics 131 (2003) 179 – 198

195

Early edges join vertices both of which have been put into a bucket before the bucket
was full, and edges for which at least one of the endpoints was placed thereafter are
called late edges.
First, observe that until one of the two buckets becomes full, both buckets havemore good internal edges than bad internal edges. So, at least one half of the earlyedges are good. But, notice that all the late edges that have one endpoint in B are also
good. This is the case since the second endpoint of a late edge is never placed in B.
Therefore, overall, there are at least 12 ( 12 − "i )M good internal edges.
To handle the external edges we add a call to Algorithm 9 right after the call to!
Algorithm 8. This algorithm counts the number mrr
is of edges between all possible pairsof buckets on di$erent processors, and broadcasts these values to all processors. Thena quick iterative algorithm is executed on each processor to ascertain as to which of
the processor’s two buckets represents the #rst and second timeslot.
After having decided the order in which the buckets are processed on processors
P1 ; : : : ; Pi−1 , we compute two values for processor Pi : A' the number of external
bad edges if we would keep the numbering of the buckets as the timeslot numbering, and A× the corresponding number if we would interchange them. Depending on
which value is less, the order of the two buckets of processor Pi is kept as-is or
exchanged.
Using the same type of argument as the one above, we get the following remark.

196

A.H. Gebremedhin et al. / Discrete Applied Mathematics 131 (2003) 179 – 198

Remark 10. Algorithm 9 ensures that overall at least 12 of the external edges are good.
Note that the above statement is true for the whole edge set, but not necessarily forthe set of edges on each processor.
Proposition 2. Algorithms 8 and 9 run with linear work and communication and in
a constant number of supersteps. The assignment of timeslots they make is such thatat least 14 of the edges are good.
Proof. For the number of good edges, let "i be the fraction of external edges ofprocessor Pi . The total amount of good edges can now be bounded from below by
% p &
(
p '
p
#
#
pM
N
1 "i
M
1 #
−
M=
=
= :
(4)
"i M +
2
4
2
4
4
4
i=1

i=1

i=1

For the complexity claim, observe that because of the load balancing done in line
balance load of Algorithm 2 (see Section 3.2.2.3) all processors hold the same amount(up to a constant factor) M " of edges.
This implies that the recursion depth is !log 4 p" (which is greater than !log2 p" of3

the average case). Moreover, more edges go into recursion here than in the averagecase and therefore the work and total communication costs are slightly greater than thecosts for the average case, but still within O(M ).
6. Conclusion
We have presented a randomized as well as a deterministic Coarse Grained Multicomputer coloring algorithm that color the vertices of a general graph G using at most
! + 1 colors, where ! is the maximum degree in G. We showed that on a p-processor
CGM model our algorithms require a parallel time of O(|G|=p) and a total work andoverall communication cost of O(|G|). These bounds correspond to the average casefor the randomized version and to the worst case for the deterministic variant. To thebest of our knowledge, our algorithms are the #rst parallel coloring algorithms withgood speedup for a large variety of architectures.
In light of the fact that LF! + 1-coloring is P-complete, a CGM LF! + 1-coloringalgorithm, if found, would be of signi#cant theoretical importance. Brent’s schedulingprinciple shows that anything that works well on PRAM should, in principle, also work
well on CGM or similar models (although the constants that are introduced might be too
big to be practical). But the converse may not necessarily be true. There are P-complete
problems (problems where we can’t expect exponential speedup on PRAM) that havepolynomial speedup [25]. It can be envisioned that such problems may as well havee"cient CGM algorithms. In this regard, our CGM ! + 1-coloring algorithm might bea #rst step towards a CGM LF! + 1-coloring algorithm.
We also believe that, in general, designing a parallel algorithm on the CGM model
is of practical relevance. In particular, we believe that the algorithms presented inA.H. Gebremedhin et al. / Discrete Applied Mathematics 131 (2003) 179 – 198

197

this paper should have e"cient and scalable implementations (i.e. implementations thatyield good speedup for a wide range of N=p).
Such implementations would also be of interest in other contexts. One example isthe problem of #nding maximal independent sets. Notice that in our algorithms thevertices colored by the least color always constitute a maximal independent set in the
input graph. In general, considering G¿i , the subgraph induced by the color classes
i; i + 1; : : : ; we see that color class i always forms a maximal independent set in thegraph G¿i .
Acknowledgements
We are grateful to the anonymous referees for their helpful comments and pointing
out some errors in an earlier version of this paper.
Isabelle Gu!erin Lassous and Jens Gustedt would like to acknowledge that part of thiswork was accomplished within the framework of the ‘operation CGM’ of the parallel
research center Centre Charles Hermitte in Nancy, France.

References[1] J.R. Allwright, R. Bordawekar, P.D. Coddington, K. Dincer, C.L. Martin, A comparison of parallelgraph coloring algorithms, Technical Report Technical Report SCCS-666, Northeast Parallel Architecture
Center, Syracuse University, 1995.
[2] G. Chaitin, M. Auslander, A. Chandra, J. Cocke, M. Hopkins, P. Markstein, Register allocation via
coloring, Comput. Languages 6 (1981) 47–57.
[3] B. Chelbus, K. Diks, W. Rytter, T. Szymacha, Parallel complexity of lexicographically #rst problems fortree-structured graphs, in: A. Kreczmar, G. Mirkowska (Eds.), Mathematical Foundations of Computer
Science 1989, Proceedings 14th Symposium, Lecture Notes in Computer Science, Vol. 379, Springer,
Berlin, 1989, pp. 185–195.
[4] T. Coleman, J. Mor!e, Estimation of sparse Jacobian matrices and graph coloring problems, SIAM J.
Numer. Anal. 20 (1) (1983) 187–209.
[5] D. Culler, R. Karp, D. Patterson, A. Sahay, K. Schauser, E. Santos, R. Subramonian, T. von Eicken,
LogP: towards a realistic model of parallel computation, in: Proceedings of the Fourth ACM SIGPLAN
Symposium on Principles and Practises of Parallel Programming, San Diego, CA, 1993, pp. 1–12.
[6] F. Dehne, A. Fabri, A. Rau-Chaplin, Scalable parallel computational geometry for coarse grained
multicomputers, Internat. J. Comput. Geom. 6 (3) (1996) 379–400.
[7] S. Fortune, J. Wyllie, Parallelism in random access machines, in: 10th ACM Symposium on Theory ofComputing, San Diego, CA, 1978, pp. 114 –118.
[8] A. Gamst, Some lower bounds for a class of frequency assignment problems, IEEE Trans. VehicularTechnol. 35 (1) (1986) 8–14.
[9] M. Garey, D. Johnson, Computers and Intractability, W.H. Freeman, New York, 1979.
[10] A.H. Gebremedhin, F. Manne, Scalable parallel graph coloring algorithms, Concurrency: Practice andExperience 12 (2000) 1131–1146.
[11] M. Goudreau, K. Lang, S. Rao, T. Suel, T. Tsantilas, Towards e"ciency and portability: programmingwith the BSP model, in: Eighth Annual ACM Symposium on Parallel Algorithms and Architectures(SPAA’96), Padua, Italy, 1996, pp. 1–12.
[12] R. Greenlaw, H. Hoover, W.L. Ruzzo, Limits to Parallel Computation: P-Completeness Theory, Oxford
University Press, New York, 1995.

198

A.H. Gebremedhin et al. / Discrete Applied Mathematics 131 (2003) 179 – 198[13] I. Gu!erin Lassous, J. Gustedt, M. Morvan, Feasability, portability, predictability and e"ciency: four
ambitious goals for the design and implementation of parallel coarse grained graph algorithms, Technical
Report 3885, INRIA, 2000a.
[14] I. Gu!erin Lassous, J. Gustedt, M. Morvan, Handling graphs according to a coarse grained approach:experiments with MPI and PVM, in: J. Dongarra, P. Kacsuk, N. Podhorszki (Eds.), Recent Advances
in Parallel Virtual Machine and Message Passing Interface, Seventh European PVM/MPI Users’ Group
Meeting, Lectures Notes in Computer Science, Vol. 1908, Springer, Berlin, 2000b, pp. 72–79.
[15] P. Hajnal, E. Szemer!edi, Brooks coloring in parallel, SIAM J. Discrete Math. 3 (1) (1990) 74–80.
[16] M.T. Jones, P.E. Plassmann, A parallel graph coloring heuristic, SIAM J. Scienti#c Comput. 14 (3)(1993) 654–669.
[17] M. Karchmer, J. Naor, A fast parallel algorithm to color a graph with D colors, J. Algorithms 9 (1)(1988) 83–91.
[18] H.J. Karlo$, An NC algorithm for Brook’s theorem, Theoret. Comput. Sci. 68 (1) (1989) 89–103.
[19] R. Karp, V. Ramachandran, Parallel algorithms for shared-memory machines, in: Handbook ofTheoretical Computer Science, Vol. A: Algorithms and Complexity, Elsevier, Amsterdam, 1990, pp.
869 –942.
[20] G. Lewandowski, Practical implementations and applications of graph coloring, Ph.D. Thesis, Universityof Wisconsin-Madison, 1994.
[21] M. Luby, A simple parallel algorithm for the maximal independent set problem, SIAM J. Comput. 15(4) (1986) 1036–1053.
[22] F. Manne, A parallel algorithm for computing the extremal eigenvalues of very large sparse matrices(extended abstract), in: Proceedings of Para98, Vol. 1541, Lecture Notes in Compouter Sciences,
Springer, Berlin, 1998, pp. 332–336.
[23] J. Naor, A fast parallel coloring of planar graphs with #ve colors, Inform. Process. Lett. 25 (1) (1987)
51–53.
[24] L.G. Valiant, A bridging model for parallel computation, Comm. ACM 33 (8) (1990) 103–111.
[25] J.S. Vitter, R.A. Simons, New classes for parallel complexity: a study of uni#cation and other complete
problems for P, IEEE Trans. Comput. C-35 (5) (1986) 403–418.