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

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

Salta

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

En este trabajo avanzamos en el estudio de la propiedad de \emph{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 \emph{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$.