Sesión Matemática Discreta y Teoría de JuegosPropiedad de 1-persistencia de la relajación clique bajo operaciones en grafos
Pablo Fekete
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 poliedral de 1-persistencia sobre la relajación clique del poliedro de conjuntos estables de un grafo \(G\), \(\mathrm{QSTAB}(G)\).
En general, un poliedro \(P\subseteq [0,1]^n\) tiene la propiedad de 1-persistencia si, para todo \(c\in\mathbb{R}^n\) y toda solución óptima \(x^*\) del problema lineal \(\max\{cx:\ x\in P\}\), existe una solución óptima entera \(y^*\) cuyas componentes satisfacen que \(y^*_j=1\) si \(x^*_j=1\).
La relajación por aristas del poliedro de conjuntos estables, \(\mathrm{FRAC}(G)\), satisface esta propiedad para todo grafo \(G\) –y también aún la versión original más fuerte de la misma, llamada persistencia [1]–, pero no ocurre así con la relajación clique. Llamando \(\mathcal{Q}\) a la familia de grafos \(G\) tales que \(\mathrm{QSTAB}(G)\) cumple la propiedad de 1-persistencia, sabemos que la operación de borrado de un nodo del grafo preserva la pertenencia a esta familia. Esto motiva una búsqueda de una caracterización de \(\mathcal{Q}\) mediante subestructuras prohibidas minimales.
Decimos que un grafo \(G\) es \(\mathrm{mn\mathcal{Q}}\) si \(G\) no pertenece a \(\mathcal{Q}\), pero todo subgrafo inducido propio sí pertenece a la familia. En trabajos previos ([2,3]) identificamos diversas familias infinitas de grafos \(\mathrm{mn\mathcal{Q}}\) asociadas a agujeros impares y sus complementos, los cuales constituyen las subestructuras prohibidas clásicas para la perfección.
Con el objetivo de profundizar la comprensión estructural de los grafos fuera de \(\mathcal{Q}\), analizamos el comportamiento de esta familia frente a operaciones de modificación en grafos. En particular analizamos variantes específicas del stretching de un nodo y la subdivisión de una arista, operaciones conocidas de la literatura, y probamos que si \(G\) no pertenece a \(\mathcal{Q}\), todo grafo obtenido de \(G\) tras alguna de estas operaciones tampoco pertenece a \(\mathcal{Q}\).
Estos resultados ofrecen un mecanismo sistemático para generar y analizar nuevas clases de grafos fuera de \(\mathcal{Q}\), constituyendo un paso clave hacia la identificación de nuevos grafos \(\mathrm{mn\mathcal{Q}}\) y la caracterización completa de la familia.
Trabajo en conjunto con: Diego Delle Donne (ESSEC Business School, France), Mariana Escalante (Universidad Nacional de Rosario y CONICET, Argentina) y Lucía Moroni (Universidad Nacional de Rosario y CONICET, Argentina).
Referencias
[1] Rodríguez-Heck, E., Stickler, K., Walter, M., Weltge, S. ``Persistency of Linear Programming Relaxations for the Stable Set Problem.'' In: 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. ``1-persistency of the clique relaxation of the stable set polytope.'' Combinatorial Optimization. Lecture Notes in Computer Science, Vol. 14594 (2024), pp. 71--84.
[3] Delle Donne, D., Escalante, M., Fekete, P., Moroni, L. ``The 1-persistency of the clique relaxation of the stable set polytope: a focus on some forbidden structures.'' Discrete Applied Mathematics, Vol. 387, (2026), pp. 37--56.