On a Representation of the Matching Polytope Via Semidefinite Liftings
Tamon Stephen, Levent Tunçel · Mathematics of Operations Research · 1999
We consider the relaxation of the matching polytope defined by the non-negativity and degree constraints. We prove that given an undirected graph on n nodes and the corresponding relaxation of the matching polytope, ⌊n/2⌋ iterations of the Lovász-Schrijver semidefinite lifting procedure are needed to obtain the matching polytope, in the worst case. We show that ⌊n/2⌋ iterations of the procedure always suffice.