Sesión Matemática DiscretaEstudios de complejidad del problema de mínima violación cromática en grafos
María Elisa Ugarte
Facultad de Ciencias Exactas, Ingeniería y Agrimensura - Universidad Nacional de Rosario, Argentina - Esta dirección de correo electrónico está siendo protegida contra los robots de spam. Necesita tener JavaScript habilitado para poder verlo.
El \emph{problema de mínima violación cromática} (PMVC) [1] es una generalización del problema clásico de coloreo de vértices (PCV). Dado un grafo $G=(V,E)$, un conjunto especial de aristas $F\subseteq E$ (a las que llamamos \emph{débiles}) y un conjunto finito $\mathcal C$ de colores, decimos que una función $\phi : V \rightarrow \mathcal C$ es un \emph{semi-coloreo} de $(G,F)$ si es un coloreo propio de $G\setminus F$ (es decir, se permite asignar el mismo color a los extremos de aristas débiles). La \emph{violación cromática} de $\phi$ sobre $(G,F)$ es el número $\nu (G,F,\phi) := | \{ij\in F: \phi(i) = \phi(j)\}|$, i.e., la cantidad de aristas débiles de $G$ cuyos extremos reciben el mismo color. El PMVC para un grafo $G$ y un conjunto de aristas débiles $F\subseteq E$ consiste en encontrar un semi-coloreo $\phi$ de $(G,F)$ con mínimo valor de $\nu (G,F,\phi)$. Este valor representa el \emph{número de violación cromática} de $(G,F)$ y se denota como $\chi_{\mathsf{v}}(G,F,\mathcal C)$. El PMVC es NP-difícil ya que el problema de hallar un coloreo de $G$ con $|\mathcal C|$ colores es el caso particular de PMVC que fija $F=\emptyset$.\\
En [1] se abordan estudios poliedrales de una formulación de programación entera para el PMVC proponiendo familias de desigualdades válidas y condiciones para que las mismas definan facetas. Por otro lado, en [2] se estudia el problema de separación de estas familias de desigualdades y se implementan rutinas de separación para un algoritmo de planos de corte.\\
En el presente trabajo estudiamos la complejidad del PMVC en distintas clases de grafos. Como resultado principal, probamos que el PMVC continúa siendo NP-difícil aún cuando nos restringimos a instancias donde $G\setminus F$ pertenece a una clase de grafos $\mathcal H$ definida en función de otra familia de grafos $\mathcal G$ para la cual el problema de \emph{precoloring extension} [3] es NP-difícil [4,5]. Esto nos permite demostrar la NP-dificultad de PMVC cuando $G\setminus F$ es un grafo de intervalos unitarios o un grafo distancia-hereditario, entre otros casos particulares. Por otro lado, proponemos y analizamos un algoritmo de tiempo polinomial para el PMVC, 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 minimum chromatic 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 Applied Combinatorial Optimization, OpenProceedings.org (2022) 17--22.
[3] M. Biró, 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án, J. Marenco, Exploring the complexity boundary between coloring and list-coloring. Annals of Operations Research - 169 (2009) 3--16.