Optimization Online


Lov\'{a}sz-Schrijver SDP-operator, near-perfect graphs and near-bipartite graphs

S. Bianchi(sbianchi***at***fceia.unr.edu.ar)
M. Escalante(mariana***at***fceia.unr.edu.ar)
G. Nasini(nasini***at***fceia.unr.edu.ar)
Levent Tuncel(ltuncel***at***math.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/2014
Entry Accepted: 11/20/2014
Entry Last Modified: 11/20/2014

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society