Sobre la familia de grafos con 1-persistencia en la relajación clique

ESCALANTE, MARIANA SILVINA; FEKETE, PABLO GABRIEL; MORONI, LUCIA

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

En este trabajo avanzamos en el estudio de la propiedad de 1-persistencia sobre la relajaci´on por cliques delpoliedro de conjuntos estables de un grafo G, QSTAB(G). En general, se dice que un poliedro P ⊂ [0, 1]ntiene la propiedad de 1-persistencia si para todo c ∈ Rn y x∗soluci´on ´optima de m´ax{cx : x ∈ P},existe una soluci´on ´optima y∗ del problema m´ax{cx : x ∈ P ∩ {0, 1}n} tal que y∗j = x∗jsi x∗j = 1. Lavalidez de esta propiedad permite el dise˜no de rutinas iterativas de b´usqueda de soluciones enteras fijandovariables en 1 en cada paso y reoptimizando sobre instancias m´as peque˜nas del problema. Esta propiedadse relaciona con otra propiedad m´as fuerte, la de 0,1-persistencia, analizada en [1].En [2,3] se demostr´o 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´en que existen grafos para los cuales estono 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. Enparticular, veremos que la familia es cerrada para la operaci´on de borrado de un nodo, y por ello quecualquier subgrafo inducido G0 de un grafo G en F tambi´en pertenece a la familia.Siendo la familia F hereditaria en ese sentido, conocer los grafos mas peque˜nos que no pertenecen a ellaimplicar´ıa una caracterizaci´on de la misma. Definimos que un grafo G es mnF si G no pertenece a Fpero todo subgrafo inducido propio s´ı est´a en la familia. En esta linea de trabajo, presentaremos unadescripci´on 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 Relaxationsfor the Stable Set Problem.” Bienstock D., Zambelli G. (eds) Integer Programming and CombinatorialOptimization. IPCO 2020. Lecture Notes in Computer Science, vol 12125. Springer, Cham.[2] Moroni, L. “Propiedad de Persistencia en la relajaci´on clique del poliedro de conjuntos estables de ungrafo.” Tesina de Licenciatura en Matem´atica. 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 larelajaci´on clique del poliedro de los conjuntos estables en un grafo”. Comunicaci´on cient´ıfica en la Reuni´onAnual de la Uni´on Matem´atica Argentina (UMA) 2022, ciudad de Neuqu´en, Argentina. Septiembre de 2022