Lovász-Schrijver SDP-operator, near-perfect graphs and near-bipartite graphs (Q517302)

The authors face the problem of characterizing the stable set polytope of \(LS_+\) (Lovasz-Schrijver lift and project operator) perfect graphs, a graph class where the maximum weight stable set problem is polynomial time solvable. The work is structured in six sections. In Section 1 and Section 2, related results of other authors from the domain of this paper are presented that will be used throughout the paper and state main characterization conjecture on \(LS_+\) perfect graphs. In Section 3 the authors characterize \(f_s\) (full-support perfection) in the family of the graphs built from a minimally imperfect graph and additional node. The validity of the conjecture on \(f_s\) perfect graphs is proved in Section 4. In Section 5, the results concerning the \(LS_+\) operator are presented and Section 6 is devoted to the conclusions and some further results.