The stable set problem and the lift-and-project ranks of graphs

作     者：Lipták, L Tunçel, L 

作者机构：Univ Waterloo Fac Math Dept Combinator & Optimizat Waterloo ON N2L 3G1 Canada 

出 版 物：《MATHEMATICAL PROGRAMMING》 

年 卷 期：2003年第98卷第1-3期

页      面：319-353页

核心收录：

学科分类：1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 070104[理学-应用数学] 0835[工学-软件工程] 0701[理学-数学] 

主　　题：stable set problem lift-and-project semidefinite lifting semidefinite programming integer programming 

摘      要：We study the lift-and-project procedures for solving combinatorial optimization problems, as described by Lovaasz and Schrijver, in the context of the stable set problem on graphs. We investigate how the procedures performances change as we apply fundamental graph operations. We show that the odd subdivision of an edge and the subdivision of a star operations (as well as their common generalization, the stretching of a vertex operation) cannot decrease the N-0-, N-, or N+-rank of the graph. We also provide graph classes (which contain the complete graphs) where these operations do not increase the N-0- or the N-rank. Hence we obtain the ranks for these graphs, and we also present some graph-minor like characterizations for them. Despite these properties we give examples showing that in general most of these operations can increase these ranks. Finally, we provide improved bounds for N+-ranks of graphs in terms of the number of nodes in the graph and prove that the subdivision of an edge or cloning a vertex can increase the N+-rank of a graph.