# Find perfect matching whose weight is minimal, in polynomial time

Given a bipartite graph $G=(A,B,E)$ and a weight function $w: E \rightarrow\mathbb{R}^+$, I'd like to find a perfect matching $M\subseteq E$ with min. weight. I'm assuming $|A| \leq |B|$, and WLOG $G$ is a complete graph (else give weight $\infty$ to non-existing edges).

Giving a variable $x_{i,j}$ for each $a_i\in A$ and $b_j\in B$, I wrote the following IP:

$$\min{\Sigma_{i,j} w(a_i,b_j)\cdot x_{i,j}}$$

$\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,$subject to $\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\, \Sigma_{j} x_{i,j}=1$ (for each $a_i\in A$)

$\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,$$\,\,\, \Sigma_{i} x_{i,j}\leq 1 (for each b_j\in B) \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,$$\,\,\, x_{i,j}\in \{ 0,1 \}$

Assuming I have the IP solution, it's obvious how to construct a min weight matching.

The only problem is that solving an IP problem is NP-Hard. Thus, I wrote the following (very similar) LP:

$$\min{\Sigma_{i,j} w(a_i,b_j)\cdot x_{i,j}}$$

$\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,$subject to $\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\, \Sigma_{j} x_{i,j}=1$ (for each $a_i\in A$)

$\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,$$\,\,\, \Sigma_{i} x_{i,j}\leq 1 (for each b_j\in B) \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,$$\,\,\, x_{i,j}\geq 0$

I've seen a proof that the IP solution value equals the LP solution value, but I'd like to find something else, I'm looking for a way to round a LP solution such that it'd be an IP solution, with the same min value!

I thought about starting from any $A$-vertex $a_i$ that doesn't have a edge with $x_{i,j}=1$. Assume $(a_i,b_j$ is the minimal weight edge for $a_i$, go to $b_j$ and check if $(a_i,b_j)$ is the min weihgt for $b_j$ too. If it is, give $x_{i,j}\leftarrow 1$ and the rest of $x_{i,j^{'}}$ and $x_{i^{'},j}$ value $0$. One problem is that I have no control over what this might affect on other vertices, meaning some other equations may not be equal $1$ now. The second problem is that if it's not the min weight for $b_j$ - so I'll have to keep going on and on, but I know that sooner or later I'll either find a pair whose min weight edge is the same or go into a cycle and that'd be a contradiction. But either way, the first problem I said already makes this useless.

Any ways to improve this method? Or perhaps other suggestions?

Thanks!

• Try to have a look at the algorithm book of Kleinberg and Tardos. It contains a good solution for your problem in Sect. 7.13 Commented Jun 1, 2015 at 14:13

Suppose we have a bipartite graph with weights on the edge, and we want to find a perfect matching whose total weight is as large as possible. Call this the maximum-weight perfect-matching problem. You can solve this problem as follows. Pick a large constant $C$ (sufficiently large); replace the weight $w$ on each edge with $w+C$ (i.e., add $C$ to each edge weight). Now find the maximum weight matching in the resulting graph using the Hungarian algorithm or any other algorithm for maximum weight matching. (Here the key fact we are using is that a maximum weight matching can be found in polynomial time.)
I claim that the resulting matching will be a perfect matching, if one exists. Why? Well, if a perfect matching exists, then its weight will be $Cn+\delta$, where $n$ is the number of edges in a perfect matching and $\delta$ is something bounded (it's the sum of $n$ weights from the original graph). The weight of any non-perfect matching will be at most $C(n-1)+\delta'$, where $\delta$ is something bounded (it's the sum of at most $n-1$ weights from the original graph). Suppose $C$ is at least $2n$ times the largest of the absolute values of the weights of the original graph. Then $Cn+\delta$ will always be larger than $C(n-1)+\delta'$, or in other words, any perfect matching will have greater total weight than any non-perfect matching. It follows that the Hungarian algorithm on this modified graph will find the maximum-weight perfect matching in the modified graph, and this corresponds to the maximum-weight perfect matching in the original graph (since we added the same constant to the weight of every edge).