The Douglas–Rachford algorithm for coloring the vertices of a graph

Abstract:

Projection algorithms are powerful tools for finding common points in a collection of sets. The convergence of these algorithms to a point in the intersection is guaranteed, provided that the involved sets are convex. In the last years, the Douglas–Rachford algorithm has received much attention, due to the good performance of the method in nonconvex scenarios, especially in combinatorial problems. In this talk, 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. We present two feasibility problems of different nature which model the problem. The good performance of the algorithm when it is applied to these formulations is demonstrated through various computational experiments.

Based on joint works with Francisco J. Aragón Artacho (University of Alicante) and Veit Elser (Cornell University).