An enhanced formulation for solving graph coloring problems with the Douglas-Rachford algorithm

Understand

We study the behavior of the Douglas-Rachford algorithm on the graph vertex-coloring problem.

• Given a graph and a number of colors, the goal is to find a coloring of the vertices so that all adjacent vertex pairs have different colors.
• In spite of the combinatorial nature of this problem, the Douglas-Rachford algorithm was recently shown to be a successful heuristic for solving a wide variety of graph coloring instances, when the problem was cast as a feasibility problem on binary indicator variables.
• In this work we consider a different formulation, based on semidefinite programming.