Two lagrangian relaxation based heuristics for vertex coloring problem

Abstract

Vertex coloring problem is a well-known NP-Hard problem where the objective is to minimizethe number of colors used to color vertices of a graph ensuring that adjacent vertices cannothave same color. In this paper, we first discuss existing mathematical formulations of theproblem and then consider two different heuristics, namely HEUR-RA and HEUR-RC, basedon Lagrangian relaxation of adjacency and coloring constraints. HEUR-RA does not requiresolving any optimization problem through execution whereas at each iteration of HEUR-RCanother NP-Hard problem, maximal weight stable set problem, is solved. We conductexperiments to observe computational performances of these heuristics. The experimentsreveal that although it requires longer running times, HEUR-RC outperforms HEUR-RA sinceit provides lower optimal gaps as well as upper bound information.