The minimum chromatic violation problem : a polyhedral approach

Abstract

In this paper we define a generalization of the classical vertex coloring problem of a graph, where some pairs of adjacent vertices can be assigned to the same color. We call weak an edge connecting two such vertices. We look for a coloring of the graph minimizing the number of weak edges having its endpoints assigned to the same color. This problem is called the minimum chromatic violation problem (MCVP). We present an integer programming formulation for this problem and provide an initial polyhedral study of the polytope arising from this formulation. We give partial characterizations of facet-inducing inequalities and we show how facets from different instances of MCVP are related. We then introduce general lifting procedures which generate (sometimes facet-inducing) valid inequalities from generic valid inequalities. We exhibit several facet-inducing families arising from these procedures and we present a family of facet-inducing inequalities which is not obtained from the prior lifting procedures, associated with certain substructures in the given graph. Finally, we analyze the extreme case of all weak edges and its relationship with the well-known k-partition problem.

En este artículo definimos una generalización del problema clásico de coloración de vértices de un gráfico, donde algunos pares de vértices adyacentes pueden asignarse al mismo color. Llamamos débil a una arista que conecta dos de esos vértices. Buscamos una coloración del gráfico minimizando el número de aristas débiles teniendo sus puntos finales asignados al mismo color. Este problema se denomina problema de violación cromática mínima (MCVP). Presentamos una formulación de programación entera para este problema y proporcionamos un estudio poliédrico inicial del politopo que surge de esta formulación. Damos caracterizaciones parciales de desigualdades que inducen facetas y mostramos cómo se relacionan las facetas de diferentes instancias de MCVP. Luego introducimos procedimientos generales de elevación que generan (a veces inducen facetas) desigualdades válidas a partir de desigualdades genéricas válidas. Mostramos varias familias inductoras de facetas que surgen de estos procedimientos y presentamos una familia de desigualdades inductoras de facetas que no se obtiene de los procedimientos de elevación anteriores, asociadas con ciertas subestructuras en el gráfico dado. Finalmente, analizamos el caso extremo de todas las aristas débiles y su relación con el conocido problema de la partición k.

Neste artigo definimos uma generalização do problema clássico de coloração de vértices de um grafo, onde alguns pares de vértices adjacentes podem ser atribuídos à mesma cor. Chamamos de fraca uma aresta que conecta dois desses vértices. Procuramos uma coloração do gráfico que minimize o número de arestas fracas tendo seus extremos atribuídos à mesma cor. Este problema é chamado de problema de violação cromática mínima (MCVP). Apresentamos uma formulação de programação inteira para este problema e fornecemos um estudo poliédrico inicial do politopo resultante desta formulação. Damos caracterizações parciais de desigualdades indutoras de facetas e mostramos como as facetas de diferentes instâncias de MCVP estão relacionadas. Em seguida, introduzimos procedimentos gerais de levantamento que geram (às vezes indutores de facetas) desigualdades válidas a partir de desigualdades válidas genéricas. Exibimos várias famílias indutoras de facetas decorrentes desses procedimentos e apresentamos uma família de desigualdades indutoras de facetas que não é obtida nos procedimentos de levantamento anteriores, associadas a certas subestruturas no gráfico fornecido. Finalmente, analisamos o caso extremo de todas as arestas fracas e sua relação com o conhecido problema da k-partição.