Sobre la propiedad de persistencia en la relajación clique del poliedro de los conjuntos estables en un grafo

DELLE DONNE DIEGO; ESCALANTE MARIANA ; FEKETE PABLO ; MORONI LUCÍA

Neuquén

Congreso; Reunión Anual de la Unión Matemática Argentina 2022; 2022

Un poliedro $Psubset [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 $cin mathbb{R}^n$ y $x^*$ solución óptima de $max{cx: xin P}$, existe una solución óptima $y^*$ del problema $max{cx: xin Pcap{0,1}^n}$ tal que $y^*_j=x^*_j$ si $x^*_jin {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$.