On the facets of lift-and-project relaxations under graph operations ?
We study the behavior of lift-and-project procedures for solving combinatorial optimization problems as described by Lovsz and Schrijver (1991) [6] in the context of the stable set problem on graphs. Following the work of Wolsey (1976) [10], Liptk and Lovsz (2001) [4] and Liptk and Tunel (2003) [5], we investigate how to generate facets of the relaxations obtained by these procedures from facets of the relaxations of the original graph, after applying fundamental graph operations. We show our findings for the odd and the star subdivision, the stretching of a node and a new operation defined herein called the clique subdivision of an edge.
stable set operations in graphs lift-and-project operators