Thursday, November 5, 2009

Integrality of the Bipartite Perfect Matching Polytope

Just to elaborate on what Yuan mentioned in class yesterday: (yet) another way to prove the integrality of the bipartite perfect matching polytope BPM is via the following fact:

Given a Delta-regular bipartite graph, it can be decomposed into Delta perfect matchings.

(The proof is via Hall's theorem: show that there exists a perfect matching in any regular bipartite graph, remove this perfect matching from the graph, and repeat.)

Suppose there was a non-integer vertex x* of BPM, note that since it is defined by some set of tight constraints with integer coefficients, this vector x* must be rational. Now you can scale the numbers by some integer C to get an integer vector Cx*. But this integer vector can be viewed as a bipartite multigraph where every vertex i has degree C(\sum_j x*_ij) = C(1) = C. Now we can use the fact above: this vector Cx* can be written as the sum of C perfect matchings.

Hence x* can be written as 1/C*this sum of perfect matchings, or a convex combination of perfect matchings, which means that it cannot itself be a vertex (extreme point) of the BPM.

No comments:

Post a Comment