Note on Lift-and-Project ranks and Antiblocker Duality

ESCALANTE MARIANA SILVINA; NASINI GRACIELA LEONOR; VARALDO MARIA DEL CARMEN

Electronic Notes in Discrete Mathematics

ELSEVIER

Lugar: The Netherlands; Año: 2004 vol. 18 p. 115 - 119

1571-0653

In Aguilera et al. (2002), it was studied the behavior of the disjunctive operator defined by Balas et al., in the context of the “antiblocker duality diagram” associated with the clique relaxation of the stable set polytope of a graph and its complement. A generalization of the Perfect Graph Theorem was obtained from the proof of the commutativity of the diagram in any number of iterations of the disjunctive operator.Lipták and Tuncel  study, in the same context, the behavior of the lift-and-project operatorsN0, N and N+ defined by Lovász and Schrijver (1991). They find a graph for which the diagram does not commute in one iteration of the N0− and N−operator. In connection with N+, the authors implicitly suggest a similar result proving that if the diagram commutes in k = O(1) iterations, P = NP.The main purpose of this work is to show that the non commutativity of the diagram can beexplicitly proved in any number of iterations of the N+−operator.