Operadores lift-and-project sobre disitntos poliedros asociados a grafos

AGUILERA, NESTOR EDGARDO; ESCALANTE, MARIANA SILVINA; FEKETE, PABLO GABRIEL

Rosario

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

Unión Matemática Argentina

Una forma de abordar problemas combinatorios que está dentro de las más fructíferas tanto en la teoría como en la práctica, es la de representar sus soluciones como los puntos enteros de un poliedro P en el hipercubo [0,1]^n. Se intenta después describir la cápsula convexa de dichos puntos, P_I (o aproximarla), a fin de optimizar un programa lineal. Estudiamos dos operadores (N y N_0) de tipo , cuya reiterada aplicación a partir de P genera una secuencia de poliedros, cada uno incluído en el anterior, que converge a P_I en a lo sumo n pasos. Definidos por Lovász y Schrijver, estos operadores fueron estudiados primero en el contexto del máximo conjunto estable en un grafo, partiendo de la relajación por aristas FRAC(G). En particular, los autores probaron que ambos operadores coinciden en la primera iteración: N_0(FRAC(G)) = N(FRAC(G)), para cualquier grafo G. Lipták y Tunçel formularon dos conjeturas relacionadas: la Conjetura N-N_0, según la cual los dos operadores coinciden en todas las sucesivas iteraciones desde FRAC(G), y la conjetura de Rangos, que afirma que el mínimo número de iteraciones necesarias para obtener la cápsula convexa de los puntos enteros de FRAC(G) (denominado rango de dicho poliedro) es igual para los dos operadores, para cualquier grafo G. Au y Tunc cel exhibieron un contraejemplo para la Conjetura N-N_0. Sin embargo, la Conjetura de Rangos permanece abierta, habiendo sido verificada para algunas familias de grafos, entre ellas, la de los grafos perfectos. Continuando trabajos anteriores en el estudio de estos operadores, sus similitudes y diferencias, en éste planteamos (y resolvemos en algunos casos) los mismos interrogantes de las conjeturas anteriores cuando se aplican los operadores sobre otra relajación de los conjuntos estables (la relajación clique) y sobre poliedros asociados a otros problemas en grafos: cubrimiento de aristas por vértices, matching y cubrimiento de vértices por aristas