On the facets of the lift-and-project relaxations of graphs subdivisions.

AGUILERA, NESTOR EDGARDO; ESCALANTE, MARIANA SILVINA; FEKETE, PABLO GABRIEL

Bariloche

Simposio; LAGOS 2011- VI Latin American Algorithms, Graphs and Optimization Symposium; 2011

We study the behavior of lift-and-project procedures for solving combinatorial optimizationproblems as described by Lovász and Schrijver (1991), in the context of the stable set problem on graphs. Following the work of Wolsey (1976), 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 subdivision of an edge and its generalization, the stretching of a vertex operation.