Some advances on Lovasz-Schrijver semidefinite programming relaxations of the fractional stable set polytope

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

DISCRETE APPLIED MATHEMATICS

ELSEVIER SCIENCE BV

Lugar: Amsterdam; Año: 2013

0166-218X

We study Lovasz and Schrijver's hieararchy of relaxations based on positivesemideniteness constraints derived from the fractional stable set polytope.We show that there are graphs G for which a single application of the underlyingoperator, N+, to the fractional stable set polytope gives a nonpolyhedralconvex relaxation of the stable set polytope. We also show that none of thecurrent best combinatorial characterizations of these relaxations obtained bya single application of the N+ operator is exact