Sobre el índice disyuntivo de grafos junta a-perfectos

BIANCHI, SILVIA MARIA; ESCALANTE, MARIANA SILVINA; MONTELAR, MARÍA SUSANA

Rosario

Congreso; LXII Reunión Anual de Comunicaciones Científicas de la Unión Matemática Argentina; 2013

Unión Matemática Argentina

En este trabajo consideramos el comportamiento del operador disyuntivo definido por Balas, Ceria y Cornu´ejols sobre la relajación clique del politopo de los conjuntos estables de los grafos junta a-perfectos definidos por Wagler. Un grafo G es junta a-perfecto si las facetas no triviales que describen su politopo de conjuntos estables, están asociadas a la junta completa de grafos antiweb primas. Desafortunadamente, no hay un algoritmo que en tiempo polinomial resuelva el problema del conjunto estable en grafos junta a-perfectos, ya que el problema de separación para desigualdades de rango asociada a los grafos antiwebs es NP-difícil. El operador disyuntivo es uno de los operadores lift-and-project, que ha sido ampliamente utilizados para la búsqueda de las desigualdades válidas para el politopo de los conjuntos estables de un grafo. Una de las principales ventajas de este operador es que conserva la estructura combinatoria del problema original. Nuestro principal objetivo es determinar una cota para el rango disyuntivo de las desigualdades que describen el politopo de los conjuntos estables de los grafos junta a-perfectos. Una cota inferior para el rango disyuntivo de una desigualdad muestra la dificultad para obtenerla, de manera que si esta es alta, puede resultar conveniente a~nadir la desigualdad directamente a la relajación lineal del problema en lugar de generarla a través de una secuencia de iteraciones del procedimiento disyuntivo. En primer lugar determinamos el rango disyuntivo de las desigualdades de rango completo de las antiwebs primas. Este resultado nos permite establecer una cota inferior tanto para el rango disyuntivo de las desigualdades asociadas, como para el ´indice disyuntivo de grafos junta a-perfectos. Por otro lado, teniendo en cuenta que el indice disyuntivo de un grafo coincide con el de su complemento, determinamos el ´indice de disyuntivo de las antiwebs y observamos que en muchos casos las desigualdades de rango completo no son las facetas de máxima profundidad de acuerdo con este operador.