Bipartite matchings via linear programming

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 P is always reached on a vertex, or, more generally, on a set of vertices of P generating an optimal face. (A vertex is a point in P that cannot be written as a nontrivial convex combination of two other points of P.)

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 \Gamma=(V,E) as a linear programming problem.

As a warmup, we treat perfect matchings. Consider the vector of |E| variables x=(x_{e_1},x_{e_2}...), and the system of inequalities

x_e\geq 0,\ e\in E,\quad \sum_{v\in e\in E} x_e=1,\ v\in V,\qquad (*)

Certainly, if x=x_M is the characteristic vector of a perfect matching M of \Gamma, i.e. x is a 0-1 vector with 1s corresponding to the edges of M, it satisfies the system (*) above. Thus maximizing the linear function \sum_{e\in E} w_e x_e on the polytope defined by (*) gives an upper bound on the size of a maximum weight perfect matching in \Gamma w.r.t. the edge weights w_e, e\in E.
But in fact much more holds: namely, this bound is tight, as follows from the following theorem.

For a bipartite graph \Gamma, the vertices of the polytope P defined by (*) have 0-1 coordinates, and are in the one-to-one correspondence with the perfect matchings of \Gamma.

Proof. Let x be a vertex of P, and X be the support of x, i.e. X=\{e\in E\mid x_e> 0\}. Then X does not contain a cycle. Indeed, a cycle in X can be decomposed into the disjoint union of two (not necessarily perfect) matchings, say M and N, as \Gamma is bipartite and so each cycle in \Gamma is even. Observe that \sum_{v\in e\in E} ((x_M)_e-(x_N)_e)=0 for any v\in V.
Thus there exists \epsilon>0 such that x\pm\epsilon(x_M-x_N)\in P, and so 2x=(x+\epsilon(x_M-x_N))+(x-\epsilon(x_M-x_N))), contradicting the assumption that x is a vertex (and so it cannot be a convex combination of two points in P).

Thus X is a forest. Let e\in X be a leaf of a subtree of X. Then (*) implies that x_e=1. Therefore any connected component of X is an edge, and so X is a matching. It is a perfect matching by (*). QED.

By this theorem, the maximum of \sum_{e\in E} w_e x_e on P is reached on a perfect matching x=x_M. Another almost immediate corollary is the following well-known result on doubly stochastic matrices (an n\times n 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, n\times n-permutation matrices (the 0-1 doubly stochastic matrices) are in one-to-one correspondence to the perfect matchings of K_{n,n}, (the characteristic vector of such a matching can be viewed as an n\times n 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 K_{n,n}, 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: , , , , ,

2 Responses to “Bipartite matchings via linear programming”

  1. MAS 720 Lecture 2 Probability in Combinatorics and Algorithms « a short fat boy and his chalkboard Says:

    […] 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. 2010 in review – Happy New Year! « Equatorial Mathematics Says:

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

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: