4
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ What exactly do you mean by a graph coloring algorithm? $\endgroup$ Jan 12, 2010 at 17:32
  • $\begingroup$ an algorithm that maps vertices to numbers from [1..k] such that no two adjacent vertices have the same number, and k is as small as possible. $\endgroup$ Jan 12, 2010 at 17:45
  • $\begingroup$ I mean an algorithm of colouring of vertices of a graph in a proper way(vertices of the same colour aren't neighbours). Not precise (It is NP-complete problem) but a rough one. Maybe somebody knows what achievements in this field are made for today. $\endgroup$
    – Oleg
    Jan 12, 2010 at 17:52
  • 4
    $\begingroup$ "heuristic" does not mean "not precise"! I know it's often used that way but that's not what it means. $\endgroup$ Jan 13, 2010 at 10:25

5 Answers 5

12
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ first link is really an awesome lecture note! thanks a lot ! $\endgroup$
    – Emadpres
    Mar 3, 2015 at 21:21
4
$\begingroup$

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.

$\endgroup$
0
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.