Stable set polytopes with high lift-and-project ranks for the Lovász-Schrijver SDP operator

• 成果类型: Article
• 署名作者: Au, Yu Hin; Tuncel, Levent
• 署名单位: University of Saskatchewan; University of Waterloo
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-024-02093-0
• 发表日期: 2025
• 页码: 79-114
• 关键词: lovasz-schrijver; stability number; convex-hull; relaxations; graph

摘要

We study the lift-and-project rank of the stable set polytopes of graphs with respect to the Lov & aacute;sz-Schrijver SDP operator LS+\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\,\textrm{LS}\,}}_+$$\end{document}. In particular, we focus on a search for relatively small graphs with high LS+\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\,\textrm{LS}\,}}_+$$\end{document}-rank (i.e., the least number of iterations of the LS+\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\,\textrm{LS}\,}}_+$$\end{document} operator on the fractional stable set polytope to compute the stable set polytope). We provide families of graphs whose LS+\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\,\textrm{LS}\,}}_+$$\end{document}-rank is asymptotically a linear function of its number of vertices, which is the best possible up to improvements in the constant factor. This improves upon the previous best result in this direction from 1999, which yielded graphs whose LS+\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\,\textrm{LS}\,}}_+$$\end{document}-rank only grew with the square root of the number of vertices.