- Lov\'{a}sz-Schrijver SDP-operator, near-perfect graphs and near-bipartite graphs S. Bianchi(sbianchifceia.unr.edu.ar) M. Escalante(marianafceia.unr.edu.ar) G. Nasini(nasinifceia.unr.edu.ar) Levent Tuncel(ltuncelmath.uwaterloo.ca) Abstract: We study the Lov\'{a}sz-Schrijver lift-and-project operator ($\LS_+$) based on the cone of symmetric, positive semidefinite matrices, applied to the fractional stable set polytope of graphs. The problem of obtaining a combinatorial characterization of graphs for which the $\LS_+$-operator generates the stable set polytope in one step has been open since 1990. We call these graphs ${\LS}_+$-\emph{perfect}. In the current contribution, we pursue a full combinatorial characterization of ${\LS}_+$-perfect graphs and make progress towards such a characterization by establishing a new, close relationship among ${\LS}_+$-perfect graphs, near-bipartite graphs and a newly introduced concept of full-support-perfect graphs. Keywords: stable set problem, lift-and-project methods, semidefinite programming, integer programming Category 1: Combinatorial Optimization Category 2: Linear, Cone and Semidefinite Programming (Semi-definite Programming ) Citation: arXiv:1411.2069, November 2014 Download: [PDF]Entry Submitted: 11/20/2014Entry Accepted: 11/20/2014Entry Last Modified: 11/20/2014Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Optmization Society.