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

DOI10.1016/J.DAM.2015.11.001MaRDI QIDQ299078zbMATH OpenOpenAlexFDO

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

Publication date 22 June 2016

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

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

zbMATH Keywords

polyhedral combinatoricswebslift-and-project operatorsstable set polytope

Mathematics Subject Classification ID

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

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.

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

Cites work

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

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)