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

2015/04/29 by Silvia Bianchi, Bianchi, S., M. Escalante +3
Computer Science · Engineering · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #FOS: Mathematics #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.1504.07888

openalex publication_date 2015/04/29 · openalex created_date 2019/06/27 · openalex updated_date 2026/07/28

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.

Citations

• A lift-and-project cutting plane algorithm for mixed 0–1 programs

Related

• Stable Set Polytopes with High Lift-and-Project Ranks for the Lovász-Schrijver SDP Operator
• Stable Set Polytopes with Rank |V(G)|/3 for the Lovász--Schrijver SDP Operator
• On Rank-Monotone Graph Operations and Minimal Obstruction Graphs for the Lovász--Schrijver SDP Hierarchy
• 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