Odd cycles break the matching LP: half-integral vertices, Edmonds' odd-set constraints, and a fractional matching proved by a vertex cover

A lab course pairs students to share a bench for the term. Nine students have said whom they can work with: each line in the figure is a possible pair. A matching picks pairs with no student in two of them, and the best one here pairs 8 of the 9 students, 4 pairs.

Now relax the rules. A pair may share a bench for part of the term: give each possible pair $e$ a share $x_{e} \geq 0$ , so that the shares at each student add up to at most one term. That is the fractional matching linear program: maximize $\sum_{e} x_{e}$ subject to $\sum_{e ∋ v} x_{e} \leq 1$ for every student $v$ . For bipartite graphs, where students come from two classes and pairs only cross, this LP always has a whole-number optimum. Triangles break that, and this problem is about how.

The LP's vertices are its corners: points that no segment inside the region passes through. Simplex-style algorithms move from vertex to vertex. A point is a vertex exactly when the constraints it meets with equality, $x_{e} = 0$ or a full student, pin it down as the only solution.

In code, students are numbered $0$ to $n - 1$ and a pair is (u, v).

Background: Polytopes and Integrality.

Part A: every student completely busy

Give every pair inside a triangle a share of $\frac{1}{2}$ , and the bridges nothing. Each student then has exactly one term, and the total is $9 \cdot \frac{1}{2}$ , that is 9/2. Nothing does better: every share is counted at two students, so twice the total is at most the 9 terms. A real pairing reaches only 4, because 9 students cannot all be paired. The LP is wrong by $\frac{1}{2}$ , and the triangles are to blame.

Part B: a corner with halves on one triangle

There are exactly three optimal vertices. One has halves on all three triangles. The other two have halves on one end triangle:

halves on $0, 1, 2$ and whole pairs $3$ – $4$ , $5$ – $6$ , $7$ – $8$ , or
halves on $6, 7, 8$ and whole pairs $0$ – $1$ , $2$ – $3$ , $4$ – $5$ .

The middle triangle cannot be the one. With halves on $3, 4, 5$ , students 3 and 5 are full, so the bridges get nothing. Each end triangle can then pair only two of its three students, and the total falls to $\frac{3}{2} + 1 + 1 = \frac{7}{2}$ .

Take the first answer. All 9 students are full, and the 5 pairs with no share give $x_{e} = 0$ . These 14 equations have rank 11, one per pair, so they pin the point down and it is a vertex. The average of the two answers is also optimal, but it is not a vertex: it lies halfway along the segment between them.

Part C: three cuts close the gap

Each triangle now carries at most 1, and the maximum drops to 4, the best real pairing. Here is a proof. Count each pair's share where it appears: in the shares at student 3, the shares at student 5, triangle $0, 1, 2$ and triangle $6, 7, 8$ . Every pair appears at least once (the middle triangle's pairs and both bridges touch student 3 or 5), and each of these four sums is at most 1. So the total is at most 4. That proof is a dual solution, and it uses two of the new constraints.

Part D: the bipartite double cover

Make a left copy $u^{'}$ and a right copy $u^{″}$ of every student. For each pair $u$ – $v$ , join $u^{'}$ to $v^{″}$ and $v^{'}$ to $u^{″}$ . The new graph is bipartite.

Matchings. A matching $M$ there gives the original pair $u$ – $v$ the share $\frac{1}{2} (number of its two copies in M)$ . Each student has two copies, each in at most one matched edge, so the shares at every student add up to at most 1. The value is $| M | / 2$ .
Covers. A vertex cover $C$ there gives student $v$ the weight $\frac{1}{2} (number of v^{'}, v^{″} in C)$ . The pair $u$ – $v$ has two copies, each covered by $C$ , so $y_{u} + y_{v} \geq 1$ . The value is $| C | / 2$ .

In a bipartite graph a maximum matching and a minimum vertex cover have the same size (Kőnig's theorem). The cover can be read off the augmenting-path search: let $Z$ be everything reachable from an unmatched left vertex by alternating paths. Then (left vertices not in $Z$ ) together with (right vertices in $Z$ ) is a minimum cover. Halving both gives the certificate the grader checks: a fractional matching and a fractional cover of equal value. The matching takes $O (n m)$ time with simple augmenting paths.

So the fractional matching LP is as easy as bipartite matching, and its optimum is always a multiple of $\frac{1}{2}$ . The hard part of general matching is getting rid of the halves, and that is what Edmonds' blossoms do.

Part E: why the corners are half-integral

Let $x$ be a vertex and look at the pairs with $0 < x_{e} < 1$ . If they contained an even cycle, or a path whose two end students are not full, add $ε$ and $- ε$ alternately along it. Both $x + ε d$ and $x - ε d$ stay feasible, so $x$ is their average and not a vertex. So the fractional pairs form vertex-disjoint cycles, each odd, with every student on them full. Round an odd cycle, consecutive shares add up to 1, so they alternate $a, 1 - a, a, \dots$ . Because the cycle is odd, the first and last share are both $a$ , which forces $a = 1 - a = \frac{1}{2}$ . The shares of 1 can share no student with anything else, so they form a matching.

Going further

Edmonds' matching polytope. With the odd-set constraint for every odd set, the LP's vertices are exactly the matchings (Edmonds, 1965). There are exponentially many constraints, but a violated one can be found in polynomial time with a minimum odd cut (Padberg and Rao), so the ellipsoid method optimizes over them. See also General Matchings.
No small formulation. Rothvoss proved that every LP whose projection is the matching polytope needs exponentially many constraints, even with extra variables.
Why bipartite is easy. Without odd cycles, the constraint matrix is totally unimodular, and every vertex is a whole-number matching. The same is true of the network flow LPs in Network Flow and Matchings.

References

J. Edmonds. Maximum matching and a polyhedron with 0,1-vertices. Journal of Research of the National Bureau of Standards 69B, 1965.
J. Edmonds. Paths, trees, and flowers. Canadian Journal of Mathematics 17, 1965.
M. W. Padberg, M. R. Rao. Odd minimum cut-sets and b-matchings. Mathematics of Operations Research 7(1), 1982.
A. Schrijver. Combinatorial Optimization: Polyhedra and Efficiency, chapters 25 and 30. Springer, 2003.
T. Rothvoss. The matching polytope has exponential extension complexity. Journal of the ACM 64(6), 2017.

The Lab Partners

Try your rule first