On the Complexity of the Minimum Chromatic Violation Problem

Abstract

In this paper, we consider a generalization of the classical vertex coloring problem of a graph, where the edge set of the graph is partitioned into strong and weak edges; the endpoints of a weak edge can be assigned to the same color and the minimum chromatic violation problem (MCVP) asks for a coloring of the graph minimizing the number of weak edges having its endpoints assigned to the same color. Previous works in the literature on MCVP focus on defining integer programming formulations and performing polyhedral studies on the associated polytopes but, to the best of our knowledge, very few computational complexity studies exist for MCVP. In this work, we focus on the computational complexity of this problem over several graph families such as interval and unit interval graphs, among others. We show that MCVP is NP-hard for general graphs and it remains NP-hard when the graph induced by the strong edges is unit interval or distance hereditary. On the other side, we provide a polynomial algorithm that properly solves MCVP when the graph is a unit interval graph without triangles with two or more weak edges.