On rank-monotone graph operations and minimal obstruction graphs for the Lovász-Schrijver SDP hierarchy

• 成果类型: Article
• 署名作者: Au, Yu Hin; Tuncel, Levent
• 署名单位: University of Saskatchewan; University of Waterloo
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-024-02166-0
• 发表日期: 2025
• 页码: 1169-1209
• 关键词: stability number; project ranks; semidefinite; relaxations

摘要

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}, with a particular focus on finding and characterizing the smallest graphs with a given 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 (the needed 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 introduce a generalized vertex-stretching operation that appears to be promising in generating 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}-minimal graphs and study its properties. We also provide several new 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}-minimal graphs, most notably the first known instances of 12-vertex graphs with 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 4, which provides the first advance in this direction since Escalante, Montelar, and Nasini's discovery of a 9-vertex graph with 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 3 in 2006.