El problema de mínima violación cromática: nuevas familias de facetas.

DELLE DONNE, DIEGO; ESCALANTE, MARIANA SILVINA; UGARTE, MARIA ELISA

Mendoza

Congreso; LXVIII Reunión Anual de Comunicaciones Científicas UMA y SOMACHI; 2019

UMA-SOMACHI

Un k-coloreo en un grafo es una partición del conjunto de vértices en k conjuntos estables. El problema clásico de coloreo de vértices (VCP) tiene como objetivo encontrar el menor k necesario para que el grafo sea k-coloreable.Continuamos nuestro estudio de una generalización del VCP, llamado el problema de la mínima violación cromática (MCVP), en el cual, dado un grafo G=(V,E), un conjunto de colores C y un subconjunto de aristas débiles F⊆E, se busca un |C|-coloreo de G′=(V,E∖F) que minimice el número de aristas de F con ambos extremos en la misma clase de color. Cuando F=∅, entonces el MCVP es el problema de k-coloreo, y por lo tanto el MCVP es NP-Difícil. Más aún, el MCVP también generaliza el problema de k-partición, cuando F=E. Aunque ya se conocen resultados poliedrales del problema de k-partición [Chopra95], existen diferencias significativas entre estos politopos y el caso general del MCVP.Basándonos en una formulación del MCVP presentada en [BDDEMUV] como problema de programación entera relacionada con la formulación estándar del VCP [DDM2016], en este trabajo avanzamos en el estudio poliedral de la cápsula convexa de las soluciones factibles del mismo.En [BDDEMUV] presentamos dos procedimientos generales de lifting que permiten generar desigualdades válidas (las cuales inducen facetas bajo ciertas hipótesis) a partir de desigualdades válidas genéricas y presentamos distintas familias de facetas, generadas por estos procedimientos.En este trabajo presentamos nuevas familias de desigualdades válidas, obtenidas mediante los mencionados procedimientos de lifting, y estudiamos su facetitud basados en la estructura particular del subgrafo a la que están asociadas.Bibliografía[BDDEMUV] Braga M., Delle Donne D., Escalante M., Marenco J., Ugarte M. E., Varaldo M. C. The minimum chromatic violation problem: a polyhedral approach. Dicrete Applied Mathematics (En prensa) (2019)[DDM2016] Delle Donne D., Marenco J. Polyhedral studies of vertex coloring problems: The standard formulation. Discrete Optimization 21 (2016) 1--13.[Chopra95] S. Chopra and M. R. Rao, Facets ok The k-partition polytope. Discrete applied mathematics 61-1 (1995) 27--48.