Sesión Matemática DiscretaPropiedad de 1-persistencia en la relajación clique del poliedro de conjuntos estables.
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.
En este trabajo avanzamos en el estudio de la propiedad de 1-persistencia sobre la relajación por cliques del poliedro de conjuntos estables de un grafo $G$, $QSTAB(G)$. En general, se dice que un poliedro $P\subset [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 [2] se demostró que, para todo grafo $G$ en cierta superclase de grafos libres de patas (paw-free), $QSTAB(G)$ verifica la propiedad de 1-persistencia, pero también que existen grafos para los cuales esto no ocurre. Llamando $Q$ a la familia de todos los grafos $G$ tales que $QSTAB(G)$ sí tiene la propiedad de 1-persistencia, probamos que cualquier subgrafo inducido $G'$ de un grafo $G$ en $Q$ también pertenece a la familia. Es por ello que la propiedad es hereditaria sobre la familia $Q$. De esta manera, conocer los grafos más "pequeños" que no pertenecen a ella llevaría a una caracterización de la misma por menores prohibidos. Definimos que un grafo $G$ es $mnQ$ si $G$ no pertenece a $Q$ pero todo subgrafo inducido por nodos propio de él, sí está en la familia. En esta línea de trabajo, en esta contribución, presentamos tres familias infinitas de estructuras mínimas prohibidas para ella.
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.