We study the lift-and-project procedures for solving combinatorial optimization problems, as described by Lov\'asz 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.
Citation
CORR 2002-13, Dept. of Combinatorics and Optimization, University of Waterloo, Ontario, CANADA, May 2002 (revised: December 2002).
Article
View The stable set problem and the lift-and-project ranks of graphs