Fractional support graph of a matching relaxation

ID: fractional-support-graph-of-a-matching-relaxation

For the degree-constrained linear programming relaxation of a matching in a graph, retain precisely the edges with fractional coordinates. In a bipartite graph, an even graph cycle in this subgraph permits alternating positive and negative perturbations preserving all vertex sums. If the subgraph is a forest, use a graph path between two tree leaves: its endpoints have positive slack and its internal sums remain unchanged. Either perturbation expresses the original feasible point as the midpoint of two distinct feasible points. Hence a fractional feasible point cannot be an extreme point, proving integrality of all extreme points of the bipartite degree relaxation.

New to topics? Read the docs here!