Linear Systems for Constrained Matching Problems
William J. Cook, William R. Pulleyblank · Mathematics of Operations Research · 1987
Each polyhedron of full dimension has a unique (up to positive scalar multiples of the inequalities) minimal defining system and a unique minimal totally dual integral defining system with integer left hand sides. These two minimal systems are characterised for the convex hull of the simple b-matchings of a graph. These characterisations are then used to provide similar characterisations for the convex hull of matchings, b-matchings, and capacitated b-matchings. Each of these characterisations gives a “best possible” min-max relation for the corresponding combinatorial objects.