Sesión Matemática DiscretaSobre la familia de grafos con 1-persistencia en la relajación clique.
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$. La validez de esta propiedad permite el diseño de rutinas iterativas de búsqueda de soluciones enteras fijando variables en 1 en cada paso y reoptimizando sobre instancias más pequeñas del problema. Esta propiedad se relaciona con otra propiedad más fuerte, la de 0,1-persistencia, analizada en [1].
En [2,3] 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 $F$ a la familia de todos los grafos $G$ tales que QSTAB($G$) sí tiene la propiedad, presentaremos resultados sobre el comportamiento de esta familia bajo algunas operaciones en grafos. En particular, veremos que la familia es cerrada para la operación de borrado de un nodo, y por ello que cualquier subgrafo inducido $G'$ de un grafo $G$ en $F$ también pertenece a la familia.
Siendo la familia $F$ hereditaria en ese sentido, conocer los grafos mas pequeños que no pertenecen a ella implicaría una caracterización de la misma. Definimos que un grafo $G$ es $mnF$ si $G$ no pertenece a $F$ pero todo subgrafo inducido propio sí está en la familia. En esta linea de trabajo, presentaremos una descripción parcial de los grafos $mnF$.
Trabajo en conjunto con: Diego Delle Donne (ESSEC Business School of Paris, Cergy-Pontoise, Francia), Mariana Escalante (Universidad Nacional de Rosario- CONICET, Argentina) y Pablo Fekete (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] Moroni, L. ``Propiedad de Persistencia en la relajación clique del poliedro de conjuntos estables de un grafo.'' Tesina de Licenciatura en Matemática. FCEIA. UNR (Aprobada el 23 de marzo de 2023).
[3] Delle Donne, D., Escalante, M., Fekete, P., Moroni, L. ``Sobre la propiedad de persistencia en la relajación clique del poliedro de los conjuntos estables en un grafo''. Comunicación científica en la Reunión Anual de la Unión Matemática Argentina (UMA) 2022, ciudad de Neuquén, Argentina. Septiembre de 2022.