Recently, Aguilera et al.\ exposed a beautiful relationship between antiblocker duality and the lift-and-project operator proposed by Balas et al. We present a very short proof of their result that the \BCC-rank of the clique polytope is invariant under complementation. The proof of Aguilera et al. relies on their main technical result, which describes a stronger duality property of all intermediate relaxations. We provide a short proof of this result, too, using simpler and more general arguments. As a result, our theorems are slightly more general. We conclude by proving that such properties do not extend to the $N_0$ and $N$ procedures of Lov\’asz and Schrijver, or to the $N_+$ procedure unless $\cP = \cNP$.
Citation
Research Report CORR 2003-16, Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario, Canada, July 2003