UMA 2022
Un poliedro $P\subset [0,1]^n$ tiene la propiedad de \emph{$0,1$-persistencia} [4] si para toda función objetivo lineal, dada una solución óptima $x^*$ del problema de optimización sobre $P$, siempre existe una solución $y^*$ del problema restringido a variables enteras tal que coincide con $x$ en todas las variables con valores 0 o 1 de ésta. Es decir, 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\in \{0,1\}.$ La validez de esta propiedad permite el diseño de rutinas iterativas de búsqueda de soluciones enteras fijando variables en 0 o 1 en cada paso y reoptimizando sobre instancias más pequeñas del problema.
Resulta conveniente distinguir esta propiedad de la que llamaremos $1$-persistencia, en la que se requiere que sólo las variables $x_j^*=1$ mantengan su valor en la solución óptima $y^*$.
En [3] se demostró que, para todo grafo $G$, la relajación por aristas del poliedro de conjuntos estables, $FRAC(G)$, tiene la propiedad de $1$-persistencia (y por lo tanto, por la estructura del problema, la $0,1$-persistencia).
Respecto a otras relajaciones propias del poliedro de los conjuntos estables distintas de $FRAC(G)$, el reciente trabajo [4] muestra que ninguna de ellas verifica la propiedad de $0,1$-persistencia para todo grafo $G$, dejando abierto en particular el interrogante sobre una caracterización de la familia $\mathcal{F}$ de grafos para los cuales la relajación por cliques, $QSTAB(G)$ sí posee la propiedad.
En este trabajo comenzamos el estudio de los grafos de la familia $\mathcal{F}$ con la propiedad de $1$-persistencia, donde pertenecen trivialmente los grafos perfectos, aquellos con clique máxima 2 y antiagujeros impares, entre otros.
Avanzando en este estudio probamos que una superclase de grafos libre de patas (paw-free) también son elementos de $\mathcal{F}$ y vale la propiedad de $1$-persistencia.
Completar una caracterización de $\mathcal{F}$ adquiere una especial relevancia en el contexto del análisis de la propiedad de $0,1$-persistencia para relajaciones del problema de coloreo de un grafo, ya que la formulación por representantes para un grafo $G$ [1,2] tiene la particularidad de coincidir con $QSTAB(G')$ para un cierto grafo $G'$ construido a partir de $G$.
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] M. Campêlo, R. Corrêa, Y. Frota, Cliques, holes and the vertex coloring polytope, Inform. Process. Lett. 89 (2004) 159-164.
[2] Delle Donne, Diego Andrés. Estudios poliedrales de problemas de coloreo de grafos. Tesis Doctoral, Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales, 2016.
[3] G. Nemhauser and L. Trotter. Vertex packings: Structural properties and algorithms. Mathematical Programming, 8(1) (1975) 232-248.
[4] E. Rodríguez-Heck, K. Stickler, M. Walter, S. Weltge. 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.