TransWikia.com

Is the matching polytope integral?

Theoretical Computer Science Asked by Karagounis Z on October 30, 2021

In this document https://courses.engr.illinois.edu/cs598csc/sp2010/Lectures/Lecture9.pdf
they prove the integrality of the matching polytope using the integrality of the perfect matching polytope.

The only part I don’t understand is on page 4-5, when they claim that $tilde x(tilde delta(U)) geq tilde x(tilde delta(X’ setminus W’)) + tilde x(tilde delta(W setminus X))$. I don’t understand why this doesn’t hold with equality, since the values on copied edges in the duplicated graph are identical.

Can someone clarify this proof? Is it a mistake?

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP