Vertex Coloring and the Min-Conflicts Algorithm

In the vertex coloring problem, you are given a graph and a set of colors. You want to assign colors to the vertices of the graph in such a way that no adjacent vertices have the same color.

The vertex coloring problem appears in a lot of different forms in the real world. To take a rather frivolous example, just consider Sudoku. Each cell corresponds to a vertex, the numbers 1-9 correspond to colors that you can assign to the vertices, and two vertices are adjacent if the corresponding cells are in the same row, column, or subgrid.

The vertex coloring problem is a constraint satisfaction problem. In a constraint satisfaction problem, you are given a set of variables, a set of possible values for each variable, and a set of constraints. You want to find an assignment of values to the variables that satisfies the constraints.

In the vertex coloring problem, the vertices are the variables, the colors are the possible values for each variable, and the constraint is that no adjacent vertices can have the same color.

There are a number of ways to solve constraint satisfaction problems. One way is recursive backtracking. The n queens problem is another constraint satisfaction problem, and I have applied recursive backtracking to solve the n queens problem.

Today I want to talk about the min-conflicts algorithm. Like simulated annealing, which I have also talked about, the min-conflicts algorithm is a type of local search. You start with some assignment of values to variables. Unless you get really lucky, that initial assignment will produce conflicts. For example, if a vertex is colored green and two of its neighboring vertices are colored green, then its being colored green produces two conflicts. So, at each iteration, the min-conflicts algorithm picks a conflicting variable at random and assigns to it a value that produces the minimal number of conflicts. If there is more than one such value, then it chooses one at random. It then repeats this process again and again, until it either finds a complete assignment of values that satisfies all of the constraints or goes through the maximum number of iterations that it may go through.

I implemented the min-conflicts algorithm, and I applied it to the vertex covering problem. I also decided to go back and apply the min-conflicts algorithm to the n queens problem. You can find more of my programs at my GitHub.