Graph Colouring with small monochromatic components
In Semester 1 2004, I did my final year computer science project on a
very new and interesting topic.
In classical graph colouring, the aim is to assign a colouring to a
graph such that no two edges have the same colour. Also, we want to
reduce the number of colours that we use to an absolute minimum. This
is a NP-Hard problem.
In graph colouring with small monochromatic components, we focus our
attention to graphs of maximum degree 4. Furthermore, we only use two
colours - black and white. The objective is to assign a colouring to
the vertices which minimise the monochromatic components.
A monochromatic component is maximal connected monochromatic subgraph.
That is, all vertices are of the same colour, and the subgraph is
connected. Maximal here means that for all vertices adjacent to some
vertex in the monochromatic component, none of these vertices are of
the same colour as the colour of the subgraph. The concept of
monochromatic component allows us to measure the performance of colour
assigments.
Very little work has actually been conducted in this specific problem.
My job was to implement two popular algorithms extracted from papers
(references in my report). The proof from the first paper (which we
implement as the EF algorithm) shows that the maximum monochromatic
component size can be bounded sublinearly in terms of the number of
vertices. The proof in the second paper (which we implement as the HST
algorithm) shows that the maximum monochromatic component size can be
bounded by a constant. However, in terms of the HST algorithm we
require an NP-hard precondition to guarentee this. In my investigation,
I devise extensions to the HST algorithm which seem to achieve this
constant bound but in Polynomial time. This is the big conjecture I
make in my work based on emperical evidence. Due to the lack of time, I
was not able to attempt to prove this.
If you've read upto here, you probably want to read my report. My
report is about 12000 words long. You probably don't want to read all
of it because it also discusses the software. THe software, on the
other hand is about 4200 lines of C code. Note that I have released the
sources under GPL. You can access then from the following links:
Latest
Update (24/01/2005)
I have decided to convert this simple toolkit into an extensible tool
for people interested in doing research, particularly with the 2 colour
problem. Currently, I will keep the toolkit limited to the 2 colour
problem, but I may possibly extend this toolkit in the near future.
Furthermore, I will begin to write a Graphical tool which will be
useful for analysis of output graphs from these algorithms. I will most
likely make this for generalised graphs right from scratch (i.e.,
rather than concentrate on the 2 colour problem). One option for
extensibility of this toolkit is to keep it very modular - so
everything is done via a plugin system. This way, when we need to work
with, say, the 2 colour problem, you can simply load the 2 colour
plugin which will have the metrics etc neccessary to work with it.
So far, I have extended the toolkit in the following ways:
- Change the static library model to a dynamic library model
- Implement a plugin architecture for the algorithms, so they can
be naturally extended by using the farmiliar dlopen() and dlsym()
functions
Currently, we're sitting on about 6000 lines of source, excluding
header files.
Download
latest source code for this software
Furthermore the following are the proposed extensions:
- Write a parameter model for each plugin. This parameter model
will be extensible - i.e., in the sense that it supports different
parameters for different algorithms, while at the same time being a
uniform interface so that it can be accessed and manipulated naturally.
One such model I have proposed is to use a standard function prototype
to manipulate the various parameters, and use a finite length array
(since each algorithm will know the parameters ahead of time) of these
pointers to functions with a string field denoting the parameter. One
other consideration is that the parameters should be arbritary.
- Seperate the parts from program/process.c which are used to run
the algorithms, process data into another shared library.
- One long term goal - write a GUI, most possibly using GTK+.
Back | Home