Treffer: On the polyhedral lift-and-project methods and the fractional stable set polytope

Abstract: We study two polyhedral lift-and-project operators (originally proposed by Lovász and Schrijver in 1991) applied to the fractional stable set polytopes. First, we provide characterizations of all valid inequalities generated by these operators. Then, we present some seven-node graphs on which the operator enforcing the symmetry of the matrix variable is strictly stronger on the odd-cycle polytope of these graphs than the operator without this symmetry requirement. This disproves a conjecture of Lipták and Tunçel from 2003. [Copyright &y& Elsevier]