\documentstyle[12pt]{article}
\title{The Graph Coloring Problem\\ Proposed Research Plan}
\author{Peter Jeavons, John Shawe-Taylor, Peter Hoare \\
(Royal Holloway, University of London) \\
Janez \v Zerovnik \\
(University of Maribor) 
\\ Toma\v z Pisanski \\
(Institute of Maths, Physics and Mechanics, Ljubljana)}
\date{January 13, 1993}
\begin{document}
\maketitle

\begin{abstract}
A mean-field annealing approach to coloring, 
with analysis of the graph adjacency
matrix to predict efficiency, and an investigation of parallel implementation.
\end{abstract}

\section{Introduction}

Our team will concentrate on coloring algorithms developed
from the stochastic method proposed by Petford and Welsh~\cite{PetWel}.
We have demonstrated that this method is equivalent to the use of
a generalised Boltzmann Machine, and this has led to some analytical
insight into the behaviour of the algorithm~\cite{STJZ92}. 
We now intend to explore a deterministic variant of this technique
based on the ideas of mean field annealing.

Initial studies have suggested that this general approach to graph coloring 
is extremely efficient for a large class of coloring problems
(and may be efficiently implemented in parallel, see \v
Zerovnik~\cite{Zer}).
However, there appears to be a well-defined, narrow range of parameters
for the underlying graph which result in the technique being
inefficient or unsuccessful. 
By analysing the relationship between the adjacency matrix
of the graph and the behaviour at each step of the mean-field annealing
algorithm, we hope to precisely identify the relevant graph parameters.

This analytical work will be supported by empirical studies investigating
the potential for parallel implementation of the algorithms developed.
The outcome of this work is expected to consist of both software
and test cases. In particular, we hope to identify specific families
of hard cases for our algorithms, which may serve as interesting test
cases for other approaches. We will therefore be using the standard
graph file format for the Challenge.

\section{Mean Field Annealing}

The technique of mean field annealing uses analogue values to
represent the state of the nodes in a graph, and these values are
updated iteratively according to a simple local update rule.
The update rule depends on a parameter, referred to as the temperature,
which is gradually reduced. At low temperatures the state of the graph
stabilises to a fixed state, and by choosing a suitable update rule
it can be arranged that these fixed states have some desired property.

This technique has been successfully applied to the graph bisection
problem, in which the nodes of a graph must be assigned to one of two
categories in such a way that the number in each category is equal,
and the number of edges between nodes of different categories is
minimised.
In this case, it has been shown~\cite{JST93} 
that the annealing process corresponds to 
finding the minimum of a global ``energy'' function
which depends on the temperature and the
adjacency matrix of the graph.
Analysis of the energy surface reveals the existence of certain critical
temperatures at which bifurcation of solutions takes place and where
computation becomes difficult. The critical temperatures depend in this
case on the spectral properties of the graph.
Hence we conjecture that
it is possible to analyse the effectiveness of the algorithm for
different classes of graphs by examining the spectrum of the adjacency
matrix.
The details of this analysis are currently under investigation.

We plan to
extend this work to the coloring problem by representing the 
colors of the nodes using (vector-valued) analogue values.
Mean field annealing may then be carried out using a suitably
adapted update rule. By analysing the corresponding energy function,
we hope to obtain a precise analytical characterisation of
what makes a graph difficult to color using this particular heuristic
algorithm.

\section{Implementation}

We shall first implement the algorithm of
\cite{PetWel} using the standard graph format of the Challenge.
The algorithm will then be modified to the mean field annealing
approach by replacing the color value of each node with a vector
of analogue values corresponding to probabilities for each color.

A parallel version of the original algorithm has been proposed in
\cite{Zer}, and it is hoped that a similar approach can be used 
to parallelize the mean field annealing version. 
In order to study the practical details of implementing these algorithms
in parallel we shall develop code for a ``Linda'' style shared memory
environment running on a local area network of Unix workstations.
Using this we shall be able to study the granularity 
and data interdependencies of
the problem and suggest appropriate parallelization strategies
and architectures for these algorithms. 

\section{Personnel}

The team for this project is based at Royal Holloway, University of London.
We will also 
be collaborating with researchers in Slovenia (Ljubljana and Maribor),
who are partners with us in a programme of research 
into algorithms for Combinatorial and Graph Theoretic problems, supported by the
European Commission.

\begin{thebibliography}{[9]}

\bibitem{PetWel} A.D.Petford, D.J.A.Welsh,
``A Randomized 3-Colouring Algorithm'', Discrete Math. 74 (1989) pp253--261.

\bibitem{STJZ92} John Shawe-Taylor, J. \v Zerovnik,
``Generalized Boltzmann Machines'', 
Proceedings of ICANN-92, North-Holland, (1992).

\bibitem{JST93} John Shawe-Taylor and Toma\v z Pisanski,
``Analysis of the Mean Field Annealing Algorithm for Graph Bisection'',
in preparation.

\bibitem{Zer} Janez \v Zerovnik,  
``A Parallel Variant of a Heuristic Algorithm for Graph Colouring'',
Parallel Computing 13 (1990), pp95--100.

\end{thebibliography}

Communication regarding this proposal should be sent to \\
P.Jeavons@dcs.rhbnc.ac.uk
\end{document}