On a representation of the matching polytope via semidefinite liftings

T. Stephen and L. Tuncel

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, $\lfloor \frac{n}{2}\rfloor$ iterations of the Lov{\'a}sz-Schrijver semidefinite lifting procedure are needed to obtain the matching polytope, in the worst case. We show that $\lfloor \frac{n}{2}\rfloor$ iterations of the procedure always suffice.

Research Report 97-11, Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario, Canada, July 1997.

Contact: ltuncel@math.uwaterloo.ca