Lóvasz-Schrijver SDP-operator, near-perfect graphs and near-bipartite graphs

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

MATHEMATICAL PROGRAMMING

SPRINGER

Lugar: Berlin; Año: 2016 vol. 162 p. 201 - 223

0025-5610

We study the Lovász-Schrijver lift-and-project operator ( LS+) based on the cone of symmetric, positivesemidefinite matrices, applied to the fractional stable set polytope of graphs. The problem of obtaining acombinatorial characterization of graphs for which the LS+-operator generates the stable set polytope inone step has been open since 1990. We call these graphs LS+-perfect. In the current contribution, wepursue a full combinatorial characterization of -perfect graphs and make progress towards such acharacterization by establishing a new, close relationship among LS+-perfect graphs, near-bipartite graphsand a newly introduced concept of full-support-perfect graphs.