Some advances on Lovász-Schrijver N+(.) relaxations of he fractional stable set polytope.

BIANCHI, SILVIA MARIA; ESCALANTE, MARIANA SILVINA; NASINI, GRACIELA LEONOR; TUNÇEL, LEVENT

Bariloche

Simposio; LAGOS 2011- VI Latin American Algorithms, Graphs and Optimization Symposium; 2011

We study Lov´asz and Schrijver’s hieararchy of relaxations based on positive semidefiniteness constraints derived from the fractional stable set polytope. We show that there are graphs G for which a single application of the underlying operator, N+, to the fractional stable set polytope gives a nonpolyhedral convex relaxation of the stable set polytope.