Find perfect matching whose weight is minimal, in polynomial time

Question

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!

Answer 1

Yes, there is a polynomial-time algorithm for your problem. There's no need to use a LP or ILP; you can solve it directly using combinatorial, graph-based methods. In particular, we can solve your problem by a reduction to the assignment problem, i.e., to computing a maximum weight matching in a weighted bipartite graph.

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).

So, there is a polynomial-time algorithm to find the perfect matching whose total weight is maximized. Given this, we can solve your problem (find the perfect matching whose total weight is minimized) by simply negating all of the edge weights.