Lovász-Schrijver SDP-operator, near-perfect graphs and near-bipartite graphs (Q517302)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Lovász-Schrijver SDP-operator, near-perfect graphs and near-bipartite graphs |
scientific article |
Statements
Lovász-Schrijver SDP-operator, near-perfect graphs and near-bipartite graphs (English)
0 references
23 March 2017
0 references
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.
0 references
stable set problem
0 references
lift and project methods
0 references
combinatorial optimization
0 references
semidefinite programming
0 references
integer programming.
0 references
0 references
0 references