Lovasz and Schrijver N+-relaxation on web graphs

ESCALANTE, MARIANA SILVINA; NASINI, GRACIELA LEONOR

Lisboa

Simposio; International Symposium in Combinatorial Optimization; 2014

ISCO

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