Sobre un procedimiento de generación de facetas para el poliedro de mínima violación cromática

BRAGA, MONICA; DELLE DONNE, DIEGO; ESCALANTE, MARIANA SILVINA; UGARTE, MARIA ELISA; VARALDO, MARIA DEL CARMEN

La Plata

Congreso; LXVII Reunión Anual de Comunicaciones Científicas de la Unión Matemática Argentina,; 2018

UMA

Un $k$-coloreo en un grafo es una partici\'on del conjunto de v\'ertices en $k$ conjuntos estables.El problema cl\'asico de coloreo de v\'ertices (VCP) tiene como objetivo encontrar el menor $k$ necesario para que el grafo sea $k$-coloreable. En la pr\'actica, no es dif\'icil encontrar situaciones en donde el valor de $k$ est\'a dado, y el objetivo es minimizar alg\'un tipo de \emph{conflicto} entre los agentes representados por v\'ertices en el grafo, pertenecientes a una misma clase de color. Con el objeto de abordar este tipo de problemas, proponemos una generalizaci\'on del VCP, llamado el \emph{problema de la m\'inima violaci\'on crom\'atica} (MCVP), en el cual, dado un grafo $G=(V,E)$, un conjunto de colores $\mathcal{C}$ y un subconjunto de aristas \emph{d\'ebiles} $F \subseteq E$, se busca un $|\mathcal{C}|$-coloreo de $G'=(V,E\setminus F)$ que minimice el n\'umero de aristas de $F$ con ambos extremos en la misma clase de color.Cuando $F = \emptyset$, entonces el MCVP es el problema de $k$-coloreo, y por lo tanto el MCVP es NP-Dif\'icil.M\'as a\'un, el MCVP tambi\'en generaliza el problema de $k$-partici\'on, cuando $F = E$. Aunque ya existen algunos estudios poliedrales del problema de $k$-partici\'on, encontramos diferencias significativas entre estos politopos y el caso general del MCVP.En este trabajo presentamos una formulaci\'on como problema de programaci\'on entera para el MCVP y abordando su estudio poliedral del mismo. En el marco del este estudio, encontramos una caracterización parcial de desigualdades que definen facetas y mostramos c\'omo est\'an relacionadas facetas de los poliedros de violación cromática de un grafo y de otro obtenido al eliminar algunas de sus aristas d\'ebiles.Introducimos dos procedimientos generales de \emph{lifting} que permiten generar desigualdades v\'alidas (las cuales inducen facetas bajo ciertas hip\'otesis) a partir de desigualdades v\'alidas gen\'ericas y presentamos distintas familias de facetas, generadas por estos procedimientos.Finalmente, mostramos una familia de facetas de tama\~no exponencial, que no es obtenida por el mencionado procedimiento de lifting, asociada a cliques con todas sus aristas débiles.