Lovasz and Schrijver N_+-Relaxation on Web Graphs

摘要

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.