\documentstyle[11pt]{article}
% page layout
\addtolength{\topmargin}{-0.8in}    % move top margin up
\setlength{\textheight}{8.85in}      % text height
\addtolength{\oddsidemargin}{-0.5in} 
\setlength{\textwidth}{6.25in}
\addtolength{\columnsep}{2.5ex}
\addtolength{\itemsep}{-1ex}
\addtolength{\topsep}{-1.5ex}
\addtolength{\parskip}{1ex}
\renewcommand{\baselinestretch}{1.2}    % double spacing

\begin{document}
\title {Parallelizing Graph Coloring Algorithms}
\author{Gary Lewandowski\thanks{email gary@cs.wisc.edu}$\;\,$ and Anne
Condon\\ Computer Sciences Department, University of Wisconsn at
Madison}
\date{}
\maketitle
\section{Introduction}
We are interested in constructing a good parallel coloring algorithm
that works well on a wide variety of graphs, and graphs of large size.
Towards this end, we propose implementing parallel versions of two
graph coloring  algorithms, XRLF and S-impasse, on the Connection
Machine CM-5.  

These two algorithms use very different strategies
to obtain a coloring of a graph.  XRLF is a successive augmentation
algorithm that colors the graph one color at a time.  Conversely, the
S-impasse algorithm is an iterative algorithm that starts from a
coloring and repeatedly moves vertices between color classes.

We hope to obtain parallel versions of these algorithms that exhibit
near-linear speedup.  We will investigate the barriers to linear
speedup, comparing the speedup possible for these two very different
coloring strategies.  We also plan to build a hybrid parallel
algorithm incorporating techniques from both of the algorithms.  We
hope this hybrid approach will give good colorings on a wide variety of 
graphs.

\section{XRLF}
The XRLF algorithm of Johnson et
al. \cite{J91} is 
an exhaustive search variant of Leighton's Recursive Largest First
(RLF) successive augmentation algorithm for graph coloring.
Studies by Johnson et al. \cite{J91} indicate that XRLF performs well on
$G_{n,p}$ graphs.  On test graphs with $p \leq 0.5$, XRLF achieves
colorings that are either the best found, or within one color of the
best coloring found.  On denser graphs, simulated annealing performs
as much as six colors better than XRLF.  XRLF performs less well on
$U_{n,p}$ geometric graphs and their complements.

The RLF algorithm colors the graph by successively choosing
independent sets; the main criterion in building the independent set
is reducing the number of edges in the remaining uncolored subgraph.
Finding the independent set that minimizes the number of
remaining edges is itself an NP-Complete problem.  The XRLF algorithm 
is more exhaustive in its search for an independent set that comes
close to fitting this
criterion.  Instead of building a single independent set, as in the
RLF algorithm, XRLF builds many {\em candidate} independent sets and
chooses the candidate set that best satisfies the criterion.  Each
candidate set is built by repeatedly looking at a constant number of
randomly chosen vertices, adding to the set the vertex that best matches
the criterion.

The XRLF algorithm is conceptually very parallelizable, since
the candidate sets can all be built independently of each other.  We
use a very simple Manager-Worker model to parallelize the algorithm.
At each step the worker processors build candidate sets and send them
back to the manager.  The manager decides which candidate is the best
independent set and uses that one for the current color, propagating
the set back to the workers who remove those nodes from their copy of
the graph.  This Manager-Worker model works well on the CM-5
architecture which has enough local memory at each processor (32 MB)
to allow each worker to keep a copy of the graph.

Further parallelism can also be introduced into the algorithm, using
Luby's parallel maximal independent set algorithm.  In this case, the
algorithm would have several groups of workers, with each group
building a candidate set.

\section{S-impasse}
The S-impasse algorithm of Morgenstern \cite{M89} is a probabilistic
iterative algorithm.  Morgenstern's experiments with S-impasse
indicate that it gives very good colorings on Leighton graphs,
$G_{n,e}$ sparse graphs, $G_{k,n,p}$ random $k$-partite graphs,
$U_{n,d}$ geometric graphs, and their complements.  It does not perform
as well on $G_{n,p}$ graphs. 

The S-impasse algorithm works by setting a goal of getting the
coloring to use only $T$ color classes.  At each step of the
algorithm, a vertex is randomly chosen from among those not in one of
the first $T$ color classes -- the impasse class.  A random target
class is then chosen from among the $T$ color classes.  A {\em move}
consists of placing the vertex into the target class and moving any
neighbors it has in the target class to the impasse class. 

A potential move is an improvement if it decreases the weighted
evaluation of the non-colored set of nodes.  This evaluation seeks to
minimize both the size and degree of the impasse class (by degree of
a set we mean the total number of edges coming from nodes in the set).
If a potential move will improve the evaluation of the impasse class,
then the S-impasse algorithm accepts the move.  If the move is a 
disimprovement, then the move is accepted only with some fixed low
probability.

As the impasse class gets small, the number of possible moves
decreases.  To counter this, the algorithm occassionaly performs an
S-chain interchange.  S-chains are a generalization of Kempe Chains.  An
S-chain is a tuple $(v, V_{0}, \ldots, V_{s-1})$ where each $V_{i}$ is
a subset of a different color class, at most one is empty and $v$ is
contained in $V_{0}$.  The sets $V_{i}$ and $V_{i+1 \bmod S}$ form Kempe
Chains.  The S-chain interchange moves the nodes in $V_{i}$ to the
nodes in the color class containing $V_{i+1 \bmod S}$, shuffling the
vertices of the coloring.  Experiments by Morgenstern indicate  
that this keeps the number of possible moves relatively large.

To parallelize this algorithm we will again use a Manager-Worker
model.  Choosing a potential move can be done independently by many
processors.  Each worker will look at moves until one is
accepted.  Upon finding an acceptable move, the worker sends it
back to the manager.  Workers may choose to do an S-chain interchange
as a part of the search for an acceptable move.  The manager will
decide which move to actually perform.  The chosen move is propagated
to the workers, who adjust their view of the solution accordingly.

The S-impasse algorithm is similar to simulated annealing algorithms
in its iterative style and acceptance of disimprovements.  Unlike
simulated annealing algorithms, it uses a fixed low probability of 
accepting a disimprovement.  Simulated annealing algorithms lower the
acceptance rate over time.  We have chosen to implement the S-impasse
algorithm because it gives results comparable to simulated annealing
coloring algorithms and is more likely to get good parallel speedup
because the low probability of acceptance gives the workers more work
to do before communicating than they have in a simulated annealing
algorithm. 
\section{Extensions}
Our Manager-Worker model and the MIMD architecture of the CM-5 allow
worker processes to use different techniques.  We plan to use this
feature to construct a hybrid of the two algorithms.  For example, as
the number of nodes left to color gets small, some of the workers
could be constructing independent sets as in the XRLF algorithm, while
others look for S-impasse moves as in the S-impasse algorithm.  We
believe the hybrid may give better colorings than are currently
achieved sequentially, and work well on many types of graphs since
each of the two algorithms performs well on some graph classes that
the other does not.   

The coarse grain of parallelism in the parallel XRLF algorithm should
allow it to be run on distributed systems that have large
communication times between processors.  If time allows, we will 
try XRLF on CondorPVM, a parallel distributed system under development
at the UW-Madison. 

\begin{small}
\begin{thebibliography}{9}
\bibitem{J91}
Johnson, D. S., C. R. Aragon, L. A. McGeoch, C. Schevon.  Optimization
by Simulated Annealing:  An Experimental Evaluation; Part II, Graph
Coloring and Number Partitioning, {\em Operations Research}, Vol. 39,
No. 3, pages 378-406, 1991.
\bibitem{M89}
Morgenstern, C. A. Algorithms for General Graph Coloring, Doctoral
Dissertation, Department of Computer Science, University of New
Mexico, Albuquerque, 1989.
\end{thebibliography}
\end{small}
\end{document}