Stable Set Polytopes with Rank |V(G)|/3 for the Lovász--Schrijver SDP Operator

2025/01/13 by Au, Yu Hin, Tunçel, Levent · 1 citation
#90C22 #90C27 #Combinatorics (math.CO) #Computational Complexity (cs.CC) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.2501.07413

Abstract

We study the lift-and-project rank of the stable set polytope of graphs with respect to the Lovász--Schrijver SDP operator LS₊ applied to the fractional stable set polytope. In particular, we show that for every positive integer ℓ, the smallest possible graph with LS₊-rank ℓ contains 3ℓ vertices. This result is sharp and settles a conjecture posed by Lipták and the second author in 2003, as well as answers a generalization of a problem posed by Knuth in 1994. We also show that for every positive integer ℓ there exists a vertex-transitive graph on 4ℓ+12 vertices with LS₊-rank at least ℓ.

Cited by

• A Computational Search for Minimal Obstruction Graphs for the Lovász--Schrijver SDP Hierarchy

Related

• Stable Set Polytopes with High Lift-and-Project Ranks for the Lovász-Schrijver SDP Operator
• On Rank-Monotone Graph Operations and Minimal Obstruction Graphs for the Lovász--Schrijver SDP Hierarchy
• A Computational Search for Minimal Obstruction Graphs for the Lovász--Schrijver SDP Hierarchy
• Lovász-Schrijver SDP-operator, near-perfect graphs and near-bipartite graphs
• Lift-and-project ranks of the stable set polytope of joined a-perfect graphs