Maximum Weight Matching Algorithm in Bipartite Graphs

Section 3.3 Maximum Weight Matching Algorithm in Bipartite Graphs

In Section 3.2, we showed how the maximum weight matching problem in bipartite graphs reduces to linear programming which, in an indirect way, implies that it is polynomial time solvable. In this section, we will get our hands dirty with describing an explicit combinatorial algorithm for finding such a maximum weight matching in practice and, at the same time, finding the vertex weighting (as in Theorem 3.2.6) which certifies maximality. This algorithm is known as the Hungarian Algorithm.

Throughout this section, we let \(G\) be a bipartite graph with bipartition \((X,Y)\) and fix a weight function \(w:E(G)\to\mathbb{R}\text{.}\) Before diving into the description of the algorithm, we start my making a few convenient simplifications. We can delete any edges of negative weight as a maximum weight matching would not include any such edges (because we could delete it and get a matching of higher weight). By adding vertices to \(G\text{,}\) we can also assume that \(|X|=|Y|\text{.}\) Also, by adding edges of weight zero, we can assume that \(G\) is complete bipartite; i.e. the edge \(xy\) is present in \(G\) for all \(x\in X\) and \(y\in Y\text{.}\) With these reductions, it is clear that seeking a maximum weight matching in the original graph is the same as finding a maximum weight perfect matching in the new balanced complete bipartite graph (since edges of weight zero have no effect). So, we assume \(G\) is a balanced complete bipartite graph and search for a maximum weight perfect matching.

Throughout the algorithm, we will maintain a function \(f:V(G)\to \mathbb{R}\) which satisfies \(f(u)+f(v)\geq w(uv)\) for all \(uv\in E(G)\) as in Theorem 3.2.6, which we call a feasible function (inspired by the fact that it corresponds to a point that is feasible for the dual linear program). During the algorithm, we say that an edge \(uv\) is tight if it satisfies \(f(u)+f(v)=w(uv)\text{.}\) Now, here is a key insight which will help us to determine when to stop the algorithm.

Lemma 3.3.1.

Given a feasible function \(f\text{,}\) if the subgraph \(H_f\) of \(G\) consisting of all edges that are tight with respect to \(f\) has a perfect matching \(M\text{,}\) then \(M\) is a perfect matching of maximum weight.

Proof.

Since every edge of \(M\) is tight, we have

\begin{equation*} \sum_{uv\in M}w(uv) = \sum_{uv\in M}(f(u)+f(v)) \end{equation*}

which, since \(M\) is a perfect matching, is equal to

\begin{equation*} \sum_{v\in V(G)}f(v). \end{equation*}

On the other hand, for any perfect matching \(M'\) in \(G\text{,}\) since \(f\) is feasible and \(M'\) is perfect, we have

\begin{equation*} \sum_{uv\in M'}w(uv) \leq \sum_{uv\in M'}(f(u)+f(v))=\sum_{v\in V(G)}f(v) \end{equation*}

and so no perfect matching can have larger weight than \(M\text{,}\) as required.

In light of Lemma 3.3.1, we can now describe a rough strategy for the algorithm. We will start with an arbitrary feasible labelling \(f\text{,}\) graph \(H_f\) of tight edges and matching \(M\) in \(H_f\) and, as long as \(M\) is not a perfect matching, we first try to find an augmenting path in \(H_f\) to make it larger. Of course, we may get stuck while building the augmenting path. However, whenever we get stuck, it will turn out that we can shift the values of the feasible function slightly to expose additional tight edges and allow us to continue building our alternating path path. Once this path reaches an unsaturated vertex, it is augmenting and we get a bigger matching. This is a rough idea of how it goes; here are the details.

Algorithm 3.3.2. The Hungarian Algorithm.

Initialize: \(f(v)=\max\left(\{w(uv):uv\in E(G)\}\cup\{0\}\right)\) for all \(v\in V(G)\text{,}\) \(H=(V(G),\emptyset)\) and \(M=\emptyset\text{.}\)
while \(M\) is not a perfect matching in \(H_f\text{,}\) do the following:
1. Let \(u\) be an \(M\)-unsaturated vertex of \(X\text{.}\)
2. Construct the set \(W\) of all vertices that can be reached by an \(M\)-alternating path in \(H_f\) starting at \(u\text{.}\) If, at any point, an unsaturated vertex \(y\in Y\) is added to \(W\text{,}\) STOP and use an \(M\)-alternating path from \(u\) to \(y\) to increase the size of the matching \(M\text{.}\) In this case, we skip step 3.
3. If the construction of \(W\) terminates and no unsaturated vertex of \(Y\) was added, define
  
  \begin{equation*} \alpha:=\min_{x\in W\cap X, y\in Y\setminus W}\left(f(x)+f(y)-w(xy)\right) \end{equation*}
  
  and modify the function \(f\) by changing \(f(v)\) to
  
  \begin{equation*} \begin{cases}f(v)-\alpha\amp \text{if }v\in X\cap W,\\ f(v)+\alpha \amp\text{if }v\in Y\cap W\\f(v)\amp\text{otherwise}.\end{cases} \end{equation*}
  
  Then update the graph \(H_f\) and go back to Step 2.
4. If \(M\) is a perfect matching in \(H_f\text{,}\) output it.

Now, let us prove that this algorithm always produces a perfect matching in \(H_f\text{.}\) First, we claim that, whenever the construction of \(W\) terminates, the value of \(\alpha\) is well-defined and positive. To see this, note that \(|W\cap X|>|W\cap Y|\) because every vertex of \(W\cap Y\) is saturated and \(W\cap X\) contains \(u\) as well as all of the vertices which share matching edges with the vertices of \(W\cap Y\text{.}\) Thus, \(W\cap X\) is non-empty and, since \(X\) and \(Y\) have the same size, \(Y\setminus W\) is non-empty as well. If there were any tight edges from \(W\cap X\) to \(Y\setminus W\text{,}\) then following one of those edges would yield an alternating path to a vertex in \(Y\setminus W\text{,}\) which contradicts the definition of \(W\text{.}\) So, since no edge from \(X\cap W\) to \(Y\setminus W\) is tight, we have \(\alpha> 0\text{.}\)

Now, we observe that, when we modify \(f\text{,}\) it remains feasible by definition of \(\alpha\) and, by construction, all of the tight edges within the set \(W\) remain tight. Also, at least one edge from \(X\cap W\) to \(Y\setminus W\) gets added to the graph \(H_f\text{.}\) So, when we go back to Step 2 , all of the alternating paths in \(W\) that we had before are still alternating and we are able to expand the size of the set \(W\) to include at least one new vertex. Since the matching \(M\) found so far is not perfect, the set \(W\) cannot expand indefinitely without incorporating an unsaturated vertex of \(Y\text{,}\) at which point we increase the size of \(M\text{.}\) So, we eventually reach a perfect matching in \(H_f\text{,}\) which is a maximum weight matching by Lemma 3.3.1. Its fairly clear that this is a polynomial time algorithm; we leave the running time analysis up to the reader.

Here is a YouTube video related to this section:

Prev Top Next