Estudio de complejidad del problema de mínima violación cromática en grafos

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

Salta

Congreso; sesión de Matemática Discreta de la XXLII Reunión Anual de Comunicaciones Científicas de la Unión Matemática Argentina; 2023

UMA

El problema de m´ınima violaci´on crom´atica (PMVC) [1] es una generalizaci´on del problema cl´asico decoloreo de v´ertices (PCV). Dado un grafo G = (V, E), un conjunto especial de aristas F ⊆ E (a las quellamamos d´ebiles) y un conjunto finito C de colores, decimos que una funci´on φ : V → C es un semi-coloreode (G, F) si es un coloreo propio de G\F (es decir, se permite asignar el mismo color a los extremos de aristas d´ebiles). La violaci´on crom´atica de φ sobre (G, F) es el n´umero ν(G, F, φ) := |{ij ∈ F : φ(i) = φ(j)}|,i.e., la cantidad de aristas d´ebiles de G cuyos extremos reciben el mismo color. El PMVC para un grafoG y un conjunto de aristas d´ebiles F ⊆ E consiste en encontrar un semi-coloreo φ de (G, F) con m´ınimovalor de ν(G, F, φ). Este valor representa el n´umero de violaci´on crom´atica de (G, F) y se denota comoχv(G, F, C). El PMVC es NP-dif´ıcil ya que el problema de hallar un coloreo de G con |C| colores es el casoparticular de PMVC que fija F = ∅.En [1] se abordan estudios poliedrales de una formulaci´on de programaci´on entera para el PMVC proponiendo familias de desigualdades v´alidas y condiciones para que las mismas definan facetas. Por otro lado,en [2] se estudia el problema de separaci´on de estas familias de desigualdades y se implementan rutinasde separaci´on para un algoritmo de planos de corte.En el presente trabajo estudiamos la complejidad del PMVC en distintas clases de grafos. Como resultadoprincipal, probamos que el PMVC contin´ua siendo NP-dif´ıcil a´un cuando nos restringimos a instanciasdonde G\F pertenece a una clase de grafos H definida en funci´on de otra familia de grafos G para la cualel problema de precoloring extension [3] es NP-dif´ıcil [4,5]. Esto nos permite demostrar la NP-dificultadde PMVC cuando G \ F es un grafo de intervalos unitarios o un grafo distancia-hereditario, entre otroscasos particulares. Por otro lado, proponemos y analizamos un algoritmo de tiempo polinomial para elPMVC, para el caso en que el grafo G pertenece a una subclase de los grafos de intervalos unitarios.Trabajo en conjunto con Diego Delle Donne (ESSEC Business School of Paris, Cergy-Pontoise, France)y Mariana Escalante (FCEIA, Universidad Nacional de Rosario - CONICET, Argentina).Referencias[1] M. Braga, D. Delle Donne, M. Escalante, J. Marenco, M. E. Ugarte, M. C. Varaldo, The minimumchromatic violation problem: a polyhedral approach. Discrete Applied Mathematics - 281 (2020) 69–80.[2] D. Delle Donne, M. Escalante, M. E. Ugarte, Implementing cutting planes for the chromatic violation problem. Proceedings of the Joint ALIO/EURO International Conference 2021-2022 on AppliedCombinatorial Optimization, OpenProceedings.org (2022) 17–22.[3] M. Bir´o, M. Hujter, Zs. Tuza, Precoloring extension. I. Interval graphs. Discrete Mathematics - 100(1992)267–279.[4] D. Marx, Precoloring extension on unit interval graphs. Discrete Applied Mathematics - 154 (2006)995– 1002.[5] F. Bonomo , G. Dur´an, J. Marenco, Exploring the complexity boundary between coloring and listcoloring. Annals of Operations Research - 169 (2009) 3–16.