On the commutativity of antiblocker diagrams under lift-and-project operators

The behavior of the disjunctive operator, defined by Balas, Ceria and Cornuéjols, in the context of the “antiblocker duality diagram” associated with the stable set polytope, QSTAB(G), of a graph and its complement, was first studied by Aguilera, Escalante and Nasini. The authors prove the commutativity of this diagram in any number of iterations of the disjunctive operator. One of the main consequences of this result is a generalization of the Perfect Graph Theorem under the disjunctive rank.In the same context, Lipták and Tunçel study the lift-and-project operators N₀, N and N₊ defined by Lovász and Schrijver. They find a graph for which the diagram does not commute in one iteration of the N₀- 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.In this paper, we give for any number of iterations, explicit proofs of the non commutativity of the N₀-, N- and N₊-diagram.In the particular case of the N₀- and N-operator, we find bounds for the ranks of the complements of line graphs (of complete graphs), which allow us to prove that the diagrams do not commute for these graphs.