An important tool for combinatorial optimisation problems, and graph problems among them, is **linear programming**, a method (and a problem) to find the optimum of a linear function on a polyhedron (i.e. on an intersection of half-spaces.) Often, such an intersection is bounded, and then one talks about a **(convex) polytope** rather than a polyhedron.

The optimum of a linear function on a polytope is always reached on a vertex, or, more generally, on a set of vertices of generating an optimal face. (A vertex is a point in that cannot be written as a nontrivial convex combination of two other points of )

Here we demonstrate a way to encode the problem of finding the size of a maximum matching (or, more generally, the maximum weight of a matching) in a bipartite graph as a linear programming problem.

As a warmup, we treat perfect matchings. Consider the vector of variables and the system of inequalities

Certainly, if is the characteristic vector of a perfect matching of i.e. is a 0-1 vector with 1s corresponding to the edges of it satisfies the system above. Thus maximizing the linear function on the polytope defined by gives an upper bound on the size of a maximum weight perfect matching in w.r.t. the edge weights

But in fact much more holds: namely, this bound is tight, as follows from the following theorem.

For a bipartite graph the vertices of the polytope defined by have 0-1 coordinates, and are in the one-to-one correspondence with the perfect matchings of

*Proof*. Let be a vertex of and be the support of i.e. Then does not contain a cycle. Indeed, a cycle in can be decomposed into the disjoint union of two (not necessarily perfect) matchings, say and as is bipartite and so each cycle in is even. Observe that for any

Thus there exists such that and so contradicting the assumption that is a vertex (and so it cannot be a convex combination of two points in ).

Thus is a forest. Let be a leaf of a subtree of Then implies that Therefore any connected component of is an edge, and so is a matching. It is a perfect matching by QED.

By this theorem, the maximum of on is reached on a perfect matching Another almost immediate corollary is the following well-known result on doubly stochastic matrices (an nonnegative real matrix is called doubly stochastic if its row and column sums are equal to 1.)

A doubly stochastic matrix is a convex combination of permutation matrices.

Indeed, -permutation matrices (the 0-1 doubly stochastic matrices) are in one-to-one correspondence to the perfect matchings of (the characteristic vector of such a matching can be viewed as an matrix, with rows corresponding to one part of the graph, and columns to the other) and so the doubly stochastic matrices are exactly the points of the perfect matching polytope of that has, by our theorem, perfect matchings as vertices (and so any point in it is a convex combination of perfect matchings).

**Excercise.** Formulate an analogy of system for matchings (not necessarily perfect) in bipartite graphs, and prove the corresponding result for vertices of the polytope in question. Using it, formulate the linear programming problem with optimal value being the size of maximum matching.

**Excercise.** Show that these constructions fail for non-bipartite graphs.

Tags: combinatorics, graph theory, MAS324, MAS445, maths, teaching

2 September, 2010 at 18:34 |

[…] and framed the problem of searching for bipartite matchings as a linear programming problem. See here for the details and here for other material on his course conducted last […]

2 January, 2011 at 22:01 |

[…] Bipartite matchings via linear programming September 20091 comment 5 […]