Índices N y N_+ para el polítopo de conjuntos estables asociado a ciertas familias de antiwebs

Resumen

Resumen: En el presente artículo, revisamos los operadores N y N_+ de levantamiento y proyección (lift-and-project) definidos porLovász y Schrijver, así como su aplicación al polítopo de conjuntos estables de un grafo. Posteriormente, estudiamos las propiedades de los índices N y N_+ asociados a estos operadores sobre la clase particular de grafos de las antiwebs. Demostramos que el índice N_+ de cualquier antiweb es igual 1, y presentamos un esquema constructivo que permite acotar elvalor del índice Npara ciertas familias de antiwebs.

Abstract: We reviewthe lift-and-project N and N+ operators defined by Lov´asz and Schrijver [3], aswell as their application
to the stable set polytope of a graph.We study the properties of the related N and N+ indices on the particular graph
class of antiwebs. We show that the N+ index related to an antiweb is equal to 1, and we propose a constructive
scheme to bound from above the N index related to certain families of antiwebs.