On Rank-Monotone Graph Operations and Minimal Obstruction Graphs for the Lovász--Schrijver SDP Hierarchy

2024/01/03 by Au, Yu Hin, Tunçel, Levent · 1 citation
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.2401.01476

Abstract

We study the lift-and-project rank of the stable set polytopes of graphs with respect to the Lovász--Schrijver SDP operator LS₊, with a particular focus on finding and characterizing the smallest graphs with a given LS₊-rank (the needed number of iterations of the LS₊ operator on the fractional stable set polytope to compute the stable set polytope). We introduce a generalized vertex-stretching operation that appears to be promising in generating LS₊-minimal graphs and study its properties. We also provide several new LS₊-minimal graphs, most notably the first known instances of 12-vertex graphs with LS₊-rank 4, which provides the first advance in this direction since Escalante, Montelar, and Nasini's discovery of a 9-vertex graph with LS₊-rank 3 in 2006.

Cited by

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

Related

• A Computational Search for Minimal Obstruction Graphs for the Lovász--Schrijver SDP Hierarchy
• 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
• 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