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

References

• [1] Aguilera NE, Escalante MS, Fekete PG (2014) On the facets of lift-and-project relaxations under graph operations. Discrete Appl. Math. 164(part 2):360–372.Crossref, Google Scholar
• [2] Au YH, Tunçel L (2016) A comprehensive analysis of polyhedral lift-and-project methods. SIAM J. Discrete Math. 30(1):411–451.Crossref, Google Scholar
• [3] Au YH, Tunçel L (2018) Elementary polytopes with high lift-and-project ranks for strong positive semidefinite operators. Discrete Optim. 27:103–129.Crossref, Google Scholar
• [4] Au YH, Tunçel L (2025) On rank-monotone graph operations and minimal obstruction graphs for the Lovász–Schrijver SDP hierarchy. Math. Programming 213(1–2):1169–1209.Crossref, Google Scholar
• [5] Au YH, Tunçel L (2025) Stable set polytopes with high lift-and-project ranks for the Lovász–Schrijver SDP operator. Math. Programming 212(1–2):79–114.Crossref, Google Scholar
• [6] Au YH, Tunçel L (2026) A computational search for minimal obstruction graphs for the Lovász–Schrijver SDP hierarchy. Preprint, submitted May 30, https://arxiv.org/abs/2505.24735.Google Scholar
• [7] Balas E, Ceria S, Cornuéjols G (1993) A lift-and-project cutting plane algorithm for mixed 0-1 programs. Math. Programming 58(3, Ser. A):295–324.Crossref, Google Scholar
• [8] Bianchi SM, Escalante MS, Nasini GL, Tunçel L (2013) Lovász–Schrijver SDP-operator and a superclass of near-perfect graphs. Electronic Notes Discrete Math. 44:339–344.Crossref, Google Scholar
• [9] Bianchi SM, Escalante MS, Nasini GL, Tunçel L (2017) Lovász–Schrijver SDP-operator, near-perfect graphs and near-bipartite graphs. Math. Programming 162(1–2, Ser. A):201–223.Crossref, Google Scholar
• [10] Bianchi SM, Escalante MS, Nasini GL, Wagler AK (2023) Lovász–Schrijver PSD-operator and the stable set polytope of claw-free graphs. Discrete Appl. Math. 332:70–86.Crossref, Google Scholar
• [11] Bienstock D, Zuckerberg M (2004) Subset algebra lift operators for 0-1 integer programming. SIAM J. Optim. 15(1):63–95.Crossref, Google Scholar
• [12] Chvátal V (1973) Edmonds polytopes and a hierarchy of combinatorial problems. Discrete Math. 4(4):305–337.Crossref, Google Scholar
• [13] Dobre C, Vera J (2015) Exploiting symmetry in copositive programs via semidefinite hierarchies. Math. Programming 151(2):659–680.Crossref, Google Scholar
• [14] Escalante MS, Montelar MS, Nasini GL (2006) Minimal N+-rank graphs: Progress on Lipták and Tunçel’s conjecture. Oper. Res. Lett. 34(6):639–646.Crossref, Google Scholar
• [15] Feige U, Krauthgamer R (2003) The probable value of the Lovász–Schrijver relaxations for maximum independent set. SIAM J. Comput. 32(2):345–370.Crossref, Google Scholar
• [16] Goemans MX, Tunçel L (2001) When does the positive semidefiniteness constraint help in lifting procedures? Math. Oper. Res. 26(4):796–815.Link, Google Scholar
• [17] Gomory RE (1958) Outline of an algorithm for integer solutions to linear programs. Bull. Amer. Math. Soc. 64(5):275–278.Crossref, Google Scholar
• [18] Gouveia J, Parrilo PA, Thomas RR (2010) Theta bodies for polynomial ideals. SIAM J. Optim. 20(4):2097–2118.Crossref, Google Scholar
• [19] Grant MC, Boyd SP (2008) Graph implementations for nonsmooth convex programs. Blondel VD, Boyd SP, Kimura H, eds. Recent Advances in Learning and Control, Lectures Notes in Control and Information Sciences, vol. 371 (Springer, London), 95–110.Crossref, Google Scholar
• [20] Grant M, Boyd S (2014) CVX: Matlab software for disciplined convex programming, version 2.1. Accessed September 17, 2026. http://cvxr.com/cvx.Google Scholar
• [21] Knuth DE (1994) The sandwich theorem. Electronic J. Combinatorics 1(1):1.Crossref, Google Scholar
• [22] Lasserre JB (2001) An explicit exact SDP relaxation for nonlinear 0-1 programs. Aardal K, Gerards B, eds. Integer Programming and Combinatorial Optimization (Utrecht, 2001), Lecture Notes in Computer Science, vol. 2081 (Springer, Berlin), 293–303.Crossref, Google Scholar
• [23] Laurent M (2001) Tighter linear and semidefinite relaxations for max-cut based on the Lovász–Schrijver lift-and-project procedure. SIAM J. Optim. 12(2):345–375.Crossref, Google Scholar
• [24] Laurent M (2003) A comparison of the Sherali-Adams, Lovász–Schrijver, and Lasserre relaxations for 0-1 programming. Math. Oper. Res. 28(3):470–496.Link, Google Scholar
• [25] Laurent M (2003) Lower bound for the number of iterations in semidefinite hierarchies for the cut polytope. Math. Oper. Res. 28(4):871–883.Link, Google Scholar
• [26] Laurent M, Vargas LF (2023) Exactness of Parrilo’s conic approximations for copositive matrices and associated low order bounds for the stability number of a graph. Math. Oper. Res. 48(2):1017–1043.Link, Google Scholar
• [27] Lipták L, Tunçel L (2003) The stable set problem and the lift-and-project ranks of graphs. Math. Program. 98(1–3, Ser. B):319–353.Crossref, Google Scholar
• [28] Lovász L, Schrijver A (1991) Cones of matrices and set-functions and 0-1 optimization. SIAM J. Optim. 1(2):166–190.Crossref, Google Scholar
• [29] Peña J, Vera J, Zuluaga LF (2007) Computing the stability number of a graph via linear and semidefinite programming. SIAM J. Optim. 18(1):87–105.Crossref, Google Scholar
• [30] Sherali HD, Adams WP (1990) A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems. SIAM J. Discrete Math. 3(3):411–430.Crossref, Google Scholar
• [31] Stephen T, Tunçel L (1999) On a representation of the matching polytope via semidefinite liftings. Math. Oper. Res. 24(1):1–7.Link, Google Scholar
• [32] Sturm JF (1999) Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones. Optim. Methods Software 11/12(1–4):625–653.Crossref, Google Scholar
• [33] Vargas LF (2023) Sum-of-squares representations for copositive matrices and independent sets in graphs. PhD thesis, Tilburg University, Tilburg, Netherlands.Google Scholar
• [34] Wagler AK (2022) On the Lovász–Schrijver PSD-operator on graph classes defined by clique cutsets. Discrete Appl. Math. 308:209–219.Crossref, Google Scholar