\documentstyle{article}
\begin{document}
\title{DIMACS Abstract: Impasse Resolution and Distributed Coloration 
Neighborhood Search}
\author{Craig Morgenstern \\
        Department of Computer Science \\
        Texas Christian University \\ \\
        {\tt morgenst@riogrande.cs.tcu.edu}}
\date{23 January 1993}
\maketitle

{\bf Classification}: (1) A new localized impasse resolution method that is both
simple and fast for four coloring large (256,000+ vertices) planar graphs
and very sparse ($m = cn$) random graphs.  (2) A distributed coloration
neighborhood search method being implemented in SR on a network of SUN 
workstations for coloring a variety of graphs, including
$K$-partite, Leighton and dense ($m = p{n \choose 2}$) random graphs.  

This abstract describes work in progress on two approaches to color
graphs.  The first,
{\it impasse resolution}, is used when a successive augmentation algorithm
is unable to assign a color to the current vertex in a sparse graph.
The second, {\it coloration neighborhood search}, is used in a simulated 
annealing framework to color dense graphs.

\section{Impasse Resolution}
When attempting to color a graph containing $m$ edges and $n$ vertices
with $k$ colors, we say that vertex $v$ is
at impasse with respect to the current partial coloration, $C$, if all $k$
colors are used in $v$'s first colored neighborhood.  An impasse resolution
method attempts to (quickly) alter $C$ so that $v$ is no longer at impasse.
The resolution methods described in \cite{algor} worked well on planar graphs
when combined into a single algorithm, but could not be successfully applied
to sparse random graphs.  In \cite{ldbt}, a new impasse resolution heuristic 
is described that is very effective on sparse random graphs (and planar graphs)
when used in conjunction with a fast implementation of the saturation ordering
method \cite{sat88,sat91}.
The new heuristic is based on the old intuition that an impasse in a sparse 
graph is a localized phenomenon, and can be resolved by recoloring a small 
colored subgraph, $H$.  

In \cite{algor}, $H$ was identified by performing a breadth-first search from 
$v$ on the colored vertices until $H$ contained no more than $L$ vertices.  
Care was taken to try to choose $L$ so that 
\begin{enumerate}
\item  $H$ was large enough to allow 
the impasse to be resolved, and 
\item $H$ was small enough so that the 
resolution attempt would not require an excessive amount of time. 
\end{enumerate}
The value for $L$ finally selected in \cite{algor}
occasionally compromised the first goal in order to always to satisfy the 
second.  When an impasse could not
be resolved, the instance was passed on to non-localized resolution method.

In \cite{ldbt}, a new heuristic is described that determines $L$ 
dynamically for each impasse.  An algorithm using this 
heuristic has successfully four colored
all the planar graph instances given in \cite{algor} as well as a set of
twenty \mbox{256,000} vertex planar graphs, all in time linear in the number 
of vertices.  Another set of experiments indicates that the heuristic is 
very effective on very sparse random graphs.
For the DIMACS challenge, we are attempting to optimize the data structures 
in the instance
generator so that planar graphs of up to \mbox{1,024,000} vertices can be 
generated and tested.  We also intend to perform more experiments on sparse
random graphs in order to determine the point at which the heuristic ceases
to be effective.

\section{Distributed Coloration Neighborhood Search}
A coloration neighborhood \cite{dsj,diss,soda} is an implicit mapping
${\cal F} : \Pi \rightarrow 2^{\Pi}$, where $\Pi$ is the
set of all colorations of a graph, and we require that the neighbors of 
$C$ given by ${\cal F}(C)$ be easily enumerable.  A coloration neighborhood
search (CNS) algorithm proceeds by traversing a neighborhood structure as
shown in Figure~\ref{fig:CNS}.
\begin{figure}[b]
\begin{center}
\begin{tabular}{|p{4in}|} \hline
\begin{tabbing}
xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx\=xxx\= \kill
$C_0$ $:=$ initial coloration; \\
repeat \+ \\
  select a $C \in {\cal F}(C_0)$; \\
  if $C$ is acceptable then $C_0$ $:=$ $C$ \- \\
until termination criteria satisfied;
\end{tabbing} \\ \hline
\end{tabular}
\end{center}
\caption{The Generic CNS Algorithm}
\label{fig:CNS}
\end{figure}

In \cite{diss,soda}, a simulated annealing based CNS algorithm is described 
that combines two distinct
neighborhood search methods into a single algorithm that outperforms both
of its components.  A brief description of the algorithm is as follows:
\begin{itemize}
\item Neighborhood ${\cal F}_1$, the ``impasse class'' neighborhood, contains
      an improper color class of vertices that are at impasse with the current 
      partial coloration given by the remaining (proper) color classes.  
      $C_2$ is a neighbor of $C_1$ if $C_2$ can be obtained from
      $C_1$ by removing some vertex, $v$, from the impasse class, adding $v$ 
      to a proper class, $V_i$, and then moving all vertices adjacent to $v$ 
      in $V_i$ to the impasse class. $C_2$ is a better coloration than $C_1$
      if $C_2$ contains fewer vertices at impasse.  Acceptance of a move was
      determined as in simulated annealing, except that the best results were
      obtained by running at an optimized fixed temperature.  A disadvantage 
      of using ${\cal F}_1$
      is that the neighborhood size becomes small as the impasse class shrinks.
      Because of this problem, the impasse class neighborhood is not 
      competitive with many of the other methods surveyed in 
      \cite{dsj,diss,soda}.
\item Neighborhood ${\cal F}_2$, the ``$s$-chain'' neighborhood, is based on
      a generalization of Kempe chaining.  
      $C_2$ is a neighbor of $C_1$ if $C_2$ can be obtained from $C_1$ by doing
      a single $s$-chain interchange.  In many types of graphs, it was found 
      that the number of $s$-chain neighbors remained fairly large, even 
      if $C_1$ was a very good coloration.
\item The combined algorithm proceeds by alternating between the two 
      neighborhoods; the structure imposed by ${\cal F}_1$ is traversed
      for some number of iterations.
      This is then followed by a sequence of random $s$-chain 
      interchanges on the proper color classes (the impasse class remains 
      unchanged).   The intuition behind this scheme
      is to move to a new solution in ${\cal F}_1$ by traversing the
      structure described by ${\cal F}_2$, and to do this more often when the
      impasse class is small.  
\item The combined algorithm was found to be competitive with numerous other
      approaches to general graph coloring on a wide variety of graphs.
\end{itemize}

For the DIMACS challenge, we propose to distribute the search amongst
several CNS processes---the processes will periodically exchange colorations in
an attempt to escape locally optimal traps.  The success of the combined
CNS algorithm described above is evidence that this approach may be able to
find better colorations than can be obtained by doing multiple runs of a single 
CNS algorithm.  We intend to implement the concurrent search in C and
SR~\cite{SR} on a network of SUN workstations.  The current design is 
that each machine will be running one of three processes:
(${\cal F}_1$)~an impasse class neighborhood search,
(${\cal F}_2$)~a $s$-chain neighborhood traversal without an objective function,
or (${\cal F}_3$)~a $s$-chain neighborhood search (with an objective function). 
These processes interact as follows:
\begin{description}
\item[${\cal F}_1$]:\ Run until termination criteria is satisfied.  If the run
improved the coloration
(i.e., if the impasse class is smaller at the end of the run), then send the
coloration to both a ${\cal F}_2$ and ${\cal F}_3$ process.  In either case, 
request a coloration from a ${\cal F}_2$ or ${\cal F}_3$ process,
and start a new run on the given coloration.

\item[${\cal F}_2$]:\ A collection of the best $B$ colorations received 
from ${\cal F}_1$ processes is maintained (based on the size of the impasse 
class).  Repeatedly loop through the colorations doing random $s$-chain
interchanges on the proper classes (the impasse class sizes do not change).
When a request is made from ${\cal F}_1$ for a new coloration, send one 
chosen randomly from the current $B$ best.  The only time a coloration is
removed from the collection is when a better one is received. 

\item[${\cal F}_3$]:\ Processes of this type are similar to those of 
type ${\cal F}_2$, except that an 
objective function and a temperature parameter is used to try to skew the
color class size distribution (in the best case, a color class becomes empty).  
\end{description}
The motivation for maintaining several colorations
in the $s$-chaining processes is that colorations fall into equivalence
classes under $s$-chaining, and it is hoped that by saving and
improving on several colorations early in the process, we will have colorations
that are representative of several equivalence classes near the end of the
process.  Finally, we mention that two refinements have recently been 
made to the impasse class search algorithm that
have resulted in speedups and/or improved performance.  The first is that
a ``rejection free'' annealing scheme \cite{rejfree} is used, and the second
is that a small tabu list \cite{tabu} is maintained when the impasse class
becomes small.  Neither of these refinements are enough to allow the
impasse class neighborhood to be competitive without $s$-chaining.  However, with
$s$-chaining, the refinements have resulted in overall speedups and in
improved performance on very dense ($p = 0.9$) random graphs, $K$-partite
graphs (with $K$ close to the expected number of colors for a random graph
with the same edge probability), and on the harder Leighton graphs.

\begin{thebibliography}{99}
  \bibitem{rejfree}
    J.\ Greene and K.\ Supowit. 1984.
    Simulated Annealing Without Rejecting Moves.
    {\it IEEE Trans.\ Computer-Aided Design}, {\bf 5}, 221--228.
  \bibitem{tabu}
    A.\ Hertz and D.\ De Werra.  1987.
    Using Tabu Search Techniques for Graph Coloring.
    {\it Computing}, {\bf 39}, 345--351.
  \bibitem{dsj}
    D.\ Johnson, C.\ Aragon, L.\ McGeoch and C.\ Schevon.  1991.
    Optimization by Simulated Annealing:  An Experimental Evaluation;
    Part II, Graph Coloring and Number Partitioning.
    {\it Operations Research}, {\bf 39}, 378--406.
  \bibitem{sat88}
    C.\ Morgenstern.  1988.
    Saturation Based Graph Coloring Algorithms.
    Tech Report CS88-1, University of New Mexico,
    Albuquerque, New Mexico.
  \bibitem{diss} C.\ Morgenstern.  1990.
    Algorithms for General Graph Coloring.
    Doctoral Dissertation, Department of Computer Science,
    University of New Mexico, Albuquerque, New Mexico.
  \bibitem{soda}
    C.\ Morgenstern and H.\ Shapiro. 1990.
    Coloration Neighborhood Structures for General Graph Coloring.
    First Annual ACM--SIAM Symposium on Discrete Algorithms.
  \bibitem{algor}
    C.\ Morgenstern and H.\ Shapiro. 1991.
    Heuristics for Rapidly Four--Coloring Large Planar Graphs.
    {\it Algorithmica}, {\bf 6}, 869--891.
  \bibitem{sat91}
    C.\ Morgenstern and H.\ Shapiro. 1991.
    Improved Implementations of Dynamic Sequential Coloring Algorithms.
    Tech Report CoSc-1991-4, Texas Christian University, Fort Worth, Texas.
  \bibitem{ldbt}
    C.\ Morgenstern, 1992.
    A New Backtracking Heuristic for Rapidly Four--Coloring Large Planar Graphs.
    Tech Report CoSc-1992-2, Texas Christian University, Fort Worth, Texas.
  \bibitem{SR}
    F.\ Andrews and R.\ Olsson. 1993.
    {\it The SR Programming Language},
    Benjamin/Cummings, Redwood City, CA.
\end{thebibliography}

\end{document}