On the commutativity of antiblocker diagrams under lift-and-project operators |
| |
Authors: | M. Escalante G. Nasini |
| |
Affiliation: | a Departamento de Matemática, Facultad de Ciencias Exactas, Ingeniería y Agrimensura, Universidad Nacional de Rosario, Argentina b Consejo Nacional de Investigaciones Científicas y Técnicas, Argentina |
| |
Abstract: | 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 N0, 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 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.In this paper, we give for any number of iterations, explicit proofs of the non commutativity of the N0-, N- and N+-diagram.In the particular case of the N0- 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. |
| |
Keywords: | Stable set problem Antiblocker duality Lift-and-project operators |
本文献已被 ScienceDirect 等数据库收录! |
|