Question

Can you suggest a good rough graph colouring algorithm? What are the best such algorithms nowadays?

Answer 1

How to write an algorithm for coloring vertices of a graph in C#?

Answer 2

There are a number of heuristics that work fairly well. They all work by prescribing some kind of ordering on the vertices, and then coloring the vertices one by one, using the least unused color to color the next one.

• First Fit does precisely the above, with an arbitrary initial ordering. It's fast, but needless to say performs rather poorly.
• LDO orders the vertices in decreasing order of degree, the idea being that the large degree vertices can be colored more easily.
• SDO (saturation degree ordering) is a variant on LDO where the vertices are ordered in decreasing order by "saturation degree", defined as the number of distinct colors in the vertex neighborhood.
• IDO (incidence degree ordering) is a variant of SDO where the "degree" of a vertex is defined as the number of colored vertices in its neighborhood.

The latter two heuristics require the order to be rebuilt after each step, and so are more expensive, but there's empirical evidence suggesting that they do reasonably well, especially in parallel.

None of these algorithms come with any kind of formal guarantees, so be warned.

Answer 3

If “heuristic graph coloring algorithms” means approximation algorithms for the chromatic number, it is very useful to read “A compendium of NP optimization problems” edited by Pierluigi Crescenzi and Viggo Kann (http://www.csc.kth.se/~viggo/wwwcompendium/node15.html), which provides references for the best-known approximability and inapproximability results as of 2000.

Answer 4

Oleg, there are also stochastic parallel approaches where you color all vertices simultaneously and randomly and apply the heuristic in parallel to all of the vertices. This mimics parallel distributed information processing in networks.

Can you give some details about the heuristic which you are working on?

Answer 5

You might find this survey article of use:

http://www.springerlink.com/content/r66452u84130n423/

Answer 6

For practical non-optimal purposes you might want to look at DSATUR, and this paper, which briefly describes some simple methods: http://www.math.tu-clausthal.de/Arbeitsgruppen/Diskrete-Optimierung/publications/2002/gca.pdf

Answer 7

An interesting approximation algorithm is the one by Wigderson. It shows how to color a 3-colorable graph with $O(\sqrt{n})$ colors. It's very simple:

If the maximum degree is less than $\sqrt{n}$, you're done (just color greedily). If there is a node of degree larger than $\sqrt{n}$, you know that it's neighborhood is two-colorable so two-color it and never use those colors again. Remove the vertex and its neighbors from the graph and continue.

There have been several follow-up works by Blum and the latest improvements use semidefinite programming.

See, for instance, http://www.cs.cmu.edu/~anupamg/adv-approx/lecture15.pdf

or,

http://www.cs.princeton.edu/~chlamtac/acc-stoc.ps

for the semidefinite programming approach.