Hybrid evolutionary search for the minimum sum coloring problem of graphs

Given a graph G, a proper k-coloring of G is an assignment of k   colors {1,…,k}{1,…,k} to the vertices of G such that two adjacent vertices receive two different colors. The minimum sum coloring problem (MSCP) is to find a proper k-coloring while minimizing the sum of the colors assigned to the vertices. This paper presents a stochastic hybrid evolutionary search algorithm for computing upper and lower bounds of this NP-hard problem. The proposed algorithm relies on a joint use of two dedicated crossover operators to generate offspring solutions and an iterated double-phase tabu search procedure to improve offspring solutions. A distance-and-quality updating rule is used to maintain a healthy diversity of the population. We show extensive experimental results to demonstrate the effectiveness of the proposed algorithm and provide the first landscape analysis of MSCP to shed light on the behavior of the algorithm.