Lift-and-project ranks of the stable set polytope of joined a-perfect graphs

DOI10.1016/J.DAM.2015.11.001zbMATH Open1339.05152arXiv1504.07888OpenAlexW750602481MaRDI QIDQ299078FDOQ299078

Authors: S. Bianchi, Mariana S. Escalante, M. S. Montelar 

Publication date: 22 June 2016

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Abstract: In this paper we study lift-and-project polyhedral operators defined by Lov?asz and Schrijver and Balas, Ceria and Cornu?ejols on the clique relaxation of the stable set polytope of web graphs. We compute the disjunctive rank of all webs and consequently of antiweb graphs. We also obtain the disjunctive rank of the antiweb constraints for which the complexity of the separation problem is still unknown. Finally, we use our results to provide bounds of the disjunctive rank of larger classes of graphs as joined a-perfect graphs, where near-bipartite graphs belong.

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

Recommendations

• The stable set problem and the lift-and-project ranks of graphs
• Lift-and-project ranks of the set covering polytope of circulant matrices
• Stability critical graphs and ranks facets of the stable set polytope
• The rank facets of the stable set polytope for claw-free graphs
• The stable set polytope and some operations on graphs
• On non-rank facets of the stable set polytope of claw-free graphs and circulant graphs
• Stable Set Polytopes for a Class of Circulant Graphs
• On the linear extension complexity of stable set polytopes for perfect graphs
• Lift-and-project cuts and perfect graphs
• The stable set polytope for some extensions of \(P_4\)-free graphs

zbMATH Keywords

polyhedral combinatoricswebslift-and-project operatorsstable set polytope

Mathematics Subject Classification ID

Perfect graphs (05C17) Polytopes and polyhedra (52B99)

Cites Work

• A class of facet producing graphs for vertex packing polyhedra
• On certain polytopes associated with graphs
• A lift-and-project cutting plane algorithm for mixed 0-1 programs
• Cones of Matrices and Set-Functions and 0–1 Optimization
• The strong perfect graph theorem
• On stable set polyhedra for K//(1,3)free graphs
• Almost integral polyhedra related to certain combinatorial optimization problems
• The rank facets of the stable set polytope for claw-free graphs
• Clique family inequalities for the stable set polytope of quasi-line graphs.
• The stable set problem and the lift-and-project ranks of graphs
• Antiwebs are rank-perfect
• Applying Lehman's theorems to packing problems
• Strength of facets for the set covering and set packing polyhedra on circulant matrices
• A comparison between lift-and-project indices and imperfection ratio on web graphs
• Comparing imperfection ratio and imperfection index for graph classes
• Stable Set Polytopes for a Class of Circulant Graphs
• Perfect zero–one matrices
• A Generalization of the Perfect Graph Theorem Under the Disjunctive Index
• Polyhedral and semidefinite programming methods in combinatorial optimization
• On the behavior of the \(N_{+}\)-operator under blocker duality

Cited In (6)

• On the commutativity of antiblocker diagrams under lift-and-project operators
• On rank-perfect subclasses of near-bipartite graphs
• On the relationship between disjunctive relaxations and minors in packing and covering problems
• Lift-and-project cuts and perfect graphs
• The stable set problem and the lift-and-project ranks of graphs
• A comparison between lift-and-project indices and imperfection ratio on web graphs

This page was built for publication: Lift-and-project ranks of the stable set polytope of joined \(a\)-perfect graphs

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