Reductions to 1–matching polyhedra
Julián Aráoz, William H. Cunningham, Jack Edmonds, Jan Green‐Krótki · Networks · 1983
Abstract The matching polyhedron theorem of Edmonds and Johnson, which gives the convex hull of capacitated perfect b‐matchings of a bidirected graph, is proved by reducing this matching problem to the ordinary perfect 1–matching problem, for which there exists a short inductive proof of the corresponding polyhedral theorem. The proof method makes it possible to deduce nestedness and discreteness properties of optimal dual solutions to the general matching problem from analogous properties of optimal dual solutions to the perfect 1–matching problem. In particular, the total dual half‐integrality of the inequality system for general matching is shown to follow from that for 1–matching. Applications considered include determining the convex hull of unions of disjoint circuits of a graph.