Sidebar

seminars:comb:abstract.201104joy

Matching, Linear Programming, and Matching Polyhedra

Abstract for the Combinatorics Seminar 2011 April 26 and 28

The techniques of linear programming provide powerful tools for studying matching problems in graph theory. Let G be a bidirected graph (a generalization of a directed graph, where each end of each edge has an independent direction) with a cost and an integral capacity associated to each edge and an integral demand b(v) at each vertex. We want a “flow” x(e) on each edge, which is nonnegative, does not exceed the capacity, is integer-valued, exactly meets the demand (the inflow to v, that is total inflow minus total outflow, equals b(v)), and has minimum cost. This is the “capacitated perfect b-matching problem” on bidirected graphs.

We can transform this into a linear programming problem by removing the integrality constraints and adding further restrictions involving odd subsets of the vertex set. Edmonds and Johnson's perfect b-matching theorem (1970) showed that the vertices of this new polytope are the minimum-cost, capacitated perfect b-matchings. This theorem can be proved by reducing it to the “perfect 1-matching problem”, which is the special case where every edge has two opposite arrows and all demands and capacities equal 1.

I will present a short proof of Edmonds' theorem on the perfect 1-matching polyhedron and a proof of the more general theorem on the perfect b-matching polyhedron for undirected graphs. Time permitting, I will present the proof of the general theorem on capacitated perfect b-matchings.

The talks are based on the papers “Reductions to 1-Matching Polyhedra” by Aráoz, Cunningham, Edmonds, and Green-Krótki (1983) and “Short Proofs on the Matching Polyhedron” by Schrijver (1983).

These talks constitute Mr. Joyce's admission-to-candidacy examination. The committee consists of Laura Anderson, Fernando Guzmán, and Thomas Zaslavsky (chair). All are welcome to attend.