Sesión Matemática Discreta1-Persistencia de la relajación clique en grafos con antiagujero impar
Lucía Moroni
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.
Un poliedro $P\subseteq [0,1]^n$ tiene la propiedad de 1-persistencia si para todo $c\in \mathbb{R}^n$ y $x^*$ solución óptima de $\max\{cx:\ x\in P\}$, existe una solución óptima $y^*$ del problema $\max\{cx:\ x\in P\cap\{0,1\}^n\}$ tal que $y^*_j=x^*_j$ si $x^*_j=1$. Esta propiedad se relaciona con otra propiedad más fuerte, la de 0,1-persistencia, analizada en [1].
En este trabajo, continuamos nuestro estudio iniciado en [2] de la 1-persistencia sobre la relajación por cliques del poliedro de conjuntos estables de un grafo $G$, $QSTAB(G)$. Si $Q$ es la familia de todos los grafos $G$ tales que $QSTAB(G)$ tiene la propiedad de 1-persistencia, probamos que esta propiedad es hereditaria en la familia $Q$ y presentamos una condición necesaria para que un grafo pertenezca a $Q$ relacionada con la presencia de una pata (paw) en el grafo, conectada de una manera específica con un agujero o antiagujero impar inducido en el grafo $G$.
A partir de estas propiedades, un grafo $G$ es $mnQ$ si $G$ no pertenece a $Q$ pero todo subgrafo inducido por nodos propio de él, está en la familia. Mientras que en [2] estudiamos los grafos $mnQ$ asociados a la presencia de patas conectadas con agujeros impares, en esta contribución, avanzamos en la caracterización de los grafos $mnQ$ construidos a partir de una pata y un antiagujero impar como subgrafo inducido. La identificación de subestructuras prohibidas para esta familia puede ser utilizada para la caracterización de los grafos $Q$-persistentes, contribuyendo al diseño de un algoritmo de Branch and Bound apropiado para el problema de optimización sobre la relajación por cliques asociada a un grafo $G$.
Trabajo en conjunto con: Delle Donne, Diego (ESSEC Business School, Cergy, France), Escalante, Mariana (CONICET, Argentina - Universidad Nacional de Rosario, Argentina) y Fekete, Pablo (Universidad Nacional de Rosario, Argentina).
Referencias
[1] E. Rodríguez-Heck, K. Stickler, M. Walter, S. Weltge. ``Persistency of Linear Programming Relaxations for the Stable Set Problem.'' Bienstock D., Zambelli G. (eds) Integer Programming and Combinatorial Optimization. IPCO 2020. Lecture Notes in Computer Science, vol 12125. Springer, Cham.
[2] Delle Donne, D., Escalante, M., Fekete, P., Moroni, L. (2024). 1-Persistency of the Clique Relaxation of the Stable Set Polytope. In: Basu, A., Mahjoub, A.R., Salazar González, J.J. (eds) Combinatorial Optimization. ISCO 2024. Lecture Notes in Computer Science, vol 14594. Springer, Cham.