Lovász and Schrijver N+-relaxation on web graphs

ESCALANTE, MARIANA SILVINA; NASINI, GRACIELA LEONOR

LECTURE NOTES IN COMPUTER SCIENCE

Springer

Lugar: New York; Año: 2014 vol. 8596 p. 221 - 230

0302-9743

In this contribution we continue the study of the Lovasz- Schrijver PSD-operator applied to the edge relaxation of the stable set polytope of a graph. The problem of obtaining a combinatorial characterization of graphs for which the PSD-operator generates the stable set polytope in one step has been open since 1990. In an earlier publication, we named these graphs N+-perfect. In the current work, we prove that the only imperfect web graphs that are N+-perfect are the odd-cycles and their complements. This result adds evidence for the validity of the conjecture stating that the only graphs which are N+-perfect are those whose stable set polytope is described by inequalities with near-bipartite support. Finally, we make some progress on identifying some minimal forbidden structures on N+-perfect graphs which are also rank-perfect.