Reductions to 1–matching polyhedra

✍ Scribed by Julian Aráoz; William H. Cunningham; Jack Edmonds; Jan Green-Krótki

• Publisher: John Wiley and Sons
• Year: 1983
• Tongue: English
• Weight: 853 KB
• Volume: 13
• Category: Article
• ISSN: 0028-3045
• DOI: 10.1002/net.3230130403

✦ Synopsis

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 t o 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 t o deduce nestednem and discreteness properties of optimal dual solutions t o the general matching problem from analogous properties of optimal dual solutions t o the perfect 1-matching problem. In particular, the total dual half- integrality of the inequality system for general matching is shown t o follow from that for 1-matching. Applications considered include determining the convex hull of unions of disjoint circuits of a graph.