Some advances on Lovász 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: 2014 vol. 164 p. 460 - 469

0166-218X

We study Lovász and Schrijver´s hieararchy of relaxations based on positive semideniteness 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. We also show that none of the current best combinatorial characterizations of these relaxations obtained by a single application of the N+ operator is exact.