106 — Simulated Annealing Algorithm for Graph Coloring

One common problem in graph theory is the task known as “graph coloring”: Given $m$ colors, find a way to color parts of a graph — namely, vertices or edges — such that no two neighbors share a color, or “label.” This is simple on small graphs, but the complexity of this challenge grows quickly with the size of a graph. This challenge is even harder if — as is very common — you don’t know the value of $m$.

If it is possible to find a coloring of the vertices of a graph such that no two neighboring vertices are the same color, the graph has “proper coloring.” There can be many different proper colorings for the same graph.

Simulated annealing is an algorithm that randomly — non-monotonically — approaches an ideal solution. I often envision it as a semi-evolutionary process (and indeed SA is commonly used for genetic algorithm simulations) where genes are randomly changed to approach a local maximum, but just as easily a mutation may occur that is not at all to the advantage of the loss-function.

Here, just as it is most often used, SA generates a very good solution, but it is not guaranteed to produce a perfect or ideal solution (a “proper coloring”). So it goes; there is as of yet no deterministic, guaranteed way to practically find an ideal graph coloring for arbitrarily large graphs.

In short, the Metropolis Algorithm Monte Carlo used in this paper randomly changes a color in the graph; if it makes the graph coloring better, assign it a high probability of staying the same. If it makes the graph coloring worse assign it a lower probability of staying the same.

In this way, the graph slowly converges on a very good (but not perfect) vertex coloring.

This sort of work is useful for a number of modern challenges: Graph coloring is a problem familiar to many people responsible for resource distribution (either in the real world or in digital terms), seating plans, sports competition scheduling, and more.