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

DOI10.1007/S10107-016-1035-1MaRDI QIDQ517302zbMATH OpenOpenAlexFDO

Authors Yong-Cai Geng, Sumit K. Garg

Publication date 23 March 2017

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1411.2069

zbMATH Keywords

combinatorial optimizationinteger programming.lift and project methodssemidefinite programmingstable set problem

Mathematics Subject Classification ID

Integer programming (90C10) Semidefinite programming (90C22) Combinatorial optimization (90C27) Programming involving graphs or networks (90C35)

Abstract: We study the Lov'asz-Schrijver lift-and-project operator ($L{S}_{+}$) 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 $L{S}_{+}$-operator generates the stable set polytope in one step has been open since 1990. We call these graphs $L{S}_{+}$-perfect. In the current contribution, we pursue a full combinatorial characterization of $L{S}_{+}$-perfect graphs and make progress towards such a characterization by establishing a new, close relationship among $L{S}_{+}$-perfect graphs, near-bipartite graphs and a newly introduced concept of full-support-perfect graphs.

Review text

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.

Recommendations

• Nikolai Ivanovich Lobachevskii (on the bicentenary of his birth)
• Lovász-Schrijver PSD-operator on some graph classes defined by clique cutsets
• On the Lovász-Schrijver PSD-operator on graph classes defined by clique cutsets
• Integrality gaps of 2-o(1) for vertex cover SDPs in the Lovász-Schrijver hierarchy
• Exact SDP relaxations for quadratic programs with bipartite graph structures
• Lovász-Schrijver PSD-operator and the stable set polytope of claw-free graphs
• Lovász-Schrijver PSD-operator on claw-free graphs
• scientific article; zbMATH DE number 637619
• scientific article; zbMATH DE number 1182569
• On rank-perfect subclasses of near-bipartite graphs

Cites work

• A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming
• An application of the Lovász-Schrijver M(K, K) operator to the stable set problem
• Applying Lehman's theorems to packing problems
• Approximation of the stability number of a graph via copositive programming
• Computing the Stability Number of a Graph Via Linear and Semidefinite Programming
• Cones of Matrices and Set-Functions and 0–1 Optimization
• Critical facets of the stable set polytope
• Further facet generating procedures for vertex packing polytopes
• Geometric algorithms and combinatorial optimization
• Lovász and Schrijver N_+-relaxation on web graphs
• Lovász-Schrijver SDP-operator, near-perfect graphs and near-bipartite graphs
• Minimal \(N_{+}\)-rank graphs: progress on Lipták and Tunçel's conjecture
• Near-perfect graphs with polyhedral N_+(G)
• Near-perfect matrices
• On certain polytopes associated with graphs
• On the facets of lift-and-project relaxations under graph operations
• On the facial structure of set packing polyhedra
• On the polyhedral lift-and-project methods and the fractional stable set polytope
• On the Shannon capacity of a graph
• Progress on perfect graphs
• Recognizing Berge graphs
• Semidefinite bounds for the stability number of a graph via sums of squares of polynomials
• Some advances on lovász-schrijver N_+() relaxations of the fractional stable set polytope
• Strong lift-and-project cutting planes for the stable set problem
• The ellipsoid method and its consequences in combinatorial optimization
• The stable set problem and the lift-and-project ranks of graphs
• The strong perfect graph theorem
• Tighter representations for set partitioning problems
• Tree-width and the Sherali-Adams operator

Cited in

(12)

• Lovász-Schrijver PSD-operator on some graph classes defined by clique cutsets
• On the Lovász-Schrijver PSD-operator on graph classes defined by clique cutsets
• Lovász-Schrijver PSD-operator and the stable set polytope of claw-free graphs
• Lovász-Schrijver PSD-operator on claw-free graphs
• Near-perfect graphs with polyhedral N_+(G)
• Characterizing N_+-perfect line graphs
• Lovász and Schrijver N_+-relaxation on web graphs
• Lovász-Schrijver SDP-operator, near-perfect graphs and near-bipartite graphs
• On connections between association schemes and analyses of polyhedral and positive semidefinite lift-and-project relaxations
• On rank-monotone graph operations and minimal obstruction graphs for the Lovász-Schrijver SDP hierarchy
• Stable set polytopes with high lift-and-project ranks for the Lovász-Schrijver SPD operator
• Application of the Lovász-Schrijver operator to compact stable set integer programs

This page was built for publication: Lovász-Schrijver SDP-operator, near-perfect graphs and near-bipartite graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q517302)