7.5.1. Minimum-Weight Perfect Matching as an LP

Recall the high-level ideas of the primal-dual schema. An algorithm based on the primal-dual schema requires a formulation of the problem to be solved as an LP \(P\), and we need the dual LP of \(P\), call it \(D\). The general strategy for finding an optimal solution to \(P\) is to start with two solutions \(\hat x\) and \(\hat y\) of \(P\) and \(D\), respectively, such that \(\hat y\) is feasible, \(\hat x\) is most likely infeasible, and \(\hat x\) and \(\hat y\) satisfy complementary slackness. The algorithm now repeatedly updates \(\hat x\) and \(\hat y\) so that complementary slackness is maintained, \(\hat y\) remains feasible, and \(\hat x\) becomes "more feasible" in every iteration. At the end, both \(\hat x\) and \(\hat y\) are feasible and satisfy complementary slackness. Thus, by Theorem 4.5, they are optimal solutions of their respective LPs.

So let us formulate the minimum-weight perfect matching problem as an LP. Actually, let us start with an ILP formulation. We associate a variable \(x_e\) with every edge. An assignment of values in \(\{0,1\}\) to these variables naturally represents a subset of edges \(M = \{e \in E \mid x_e = 1\}\). We want to choose \(M\) to be a minimum-weight perfect matching. Thus, we want to minimize the objective function

\[\sum_{e \in E} c_ex_e,\]

subject to appropriate constraints that guarantee that \(M\) is a perfect matching. Throughout this section, we use \(c_e\) to refer to the cost of the edge \(e\).

If \(|U| = |W| = n\), then a perfect matching has size \(n\):

\[\sum_{e \in E} x_e = n.\]

\(M\) is a matching if it contains at most one of the edges incident to each vertex:

\[\begin{aligned} \sum_{w \in W} x_{u,w} &\le 1 \quad \forall u \in U,\\ \sum_{u \in U} x_{u,w} &\le 1 \quad \forall w \in W. \end{aligned}\]

This gives the following complete ILP formulation of the minimum-weight perfect matching problem:

\[\begin{gathered} \text{Minimize}\ \sum_{e \in E} c_ex_e\\ \begin{aligned} \text{s.t.}\ \sum_{e \in E} x_e &\ge n\\ \sum_{w \in W} x_{u,w} &\le 1 && \forall u \in U\\ \sum_{u \in U} x_{u,w} &\le 1 && \forall w \in W\\ x_e &\in \{0, 1\} && \forall e \in E. \end{aligned} \end{gathered}\tag{7.1}\]

We turned the equality constraint \(\sum_{e \in E} x_e = n\) into an inequality \(\sum_{e \in E} x_e \ge n\) because the upper bound \(\sum_{e \in E} x_e \le n\) is redundant: If \(\sum_{e \in E} x_e \ge n\) and \(\sum_{w \in W} x_{u,w} \le 1\) for all \(u \in U\), then we must have \(\sum_{e \in E} x_e = n\), \(\sum_{w \in W} x_{u,w} = 1\) for all \(u \in U\), and \(\sum_{u \in U} x_{u,w} = 1\) for all \(w \in W\).

The LP relaxation of (7.1) is

\[\begin{gathered} \text{Minimize}\ \sum_{e \in E} c_ex_e\\ \begin{aligned} \text{s.t.}\ \sum_{e \in E} x_e &\ge n\\ \sum_{w \in W} x_{u,w} &\le 1 && \forall u \in U\\ \sum_{u \in U} x_{u,w} &\le 1 && \forall w \in W\\ x_e &\ge 0 && \forall e \in E. \end{aligned} \end{gathered}\tag{7.2}\]

Note that we omitted the upper bound constraint \(x_e \le 1\) for every edge \(e \in E\). This constraint is also redundant because for all \((u,w) \in E\), \(x_{u,w} \le 1\) follows from the constraints \(\sum_{w' \in W} x_{u,w'} \le 1\) and \(x_{u,w'} \ge 0\) for all \((u,w') \in E\).

The Hungarian Algorithm finds an integral optimal solution of (7.2). Thus, it is also an optimal solution of (7.1) and is therefore a minimum-weight perfect matching.

The dual of (7.2) is

\[\begin{gathered} \text{Maximize } nz - \sum_{u \in U} y_u - \sum_{w \in W} y_w\\ \begin{aligned} \text{s.t.}\ z - y_u - y_w &\le c_{u,w} && \forall (u,w) \in E\\ y_u &\ge 0 && \forall u \in U\\ y_w &\ge 0 && \forall w \in W\\ z &\ge 0. \end{aligned} \end{gathered}\tag{7.3}\]

Here, \(z\) is the dual variable corresponding to the first primal constraint, \(y_u\) is the dual variable corresponding to the constraint \(\sum_{w \in W} x_{u,w} \le 1\) associated with the vertex \(u \in U\), and \(y_w\) is the dual variable corresponding to the constraint \(\sum_{u \in U} x_{u,w} \le 1\) associated with the vertex \(w \in W\).

Now remember that we want to find a feasible primal solution \(\hat x\) and a feasible dual solution \(\bigl(\hat z, \hat y\bigr)\) that satisfy complementary slackness. The complementary slackness conditions for the two LPs (7.2) and (7.3) are

\begin{align} \sum_{e \in E} x_e &= n && \text{or} & z &= 0\tag{7.4}\\ \sum_{w \in W} x_{u,w} &= 1 && \text{or} & y_u &= 0 && \forall u \in U\tag{7.5}\\ \sum_{u \in U} x_{u,w} &= 1 && \text{or} & y_w &= 0 && \forall w \in W\tag{7.6}\\ z - y_u - y_v &= c_{u, w} && \text{or} & x_{u,w} &= 0 && \forall (u,w) \in E.\tag{7.7} \end{align}

As observed above, conditions (7.4)–(7.6) are satisfied by every feasible primal solution, so we can ignore them. This leaves us with (7.7). As we will see shortly, this condition has a very natural interpretation, which forms the basis of the Hungarian Algorithm.

Let us clean up the dual a little. We associate a new variable \(\pi_u = z - y_u\) with every vertex \(u \in U\) and a new variable \(\pi_w = -y_w\) with every vertex \(w \in W\). Substituting these variables into (7.3) gives the LP

\[\begin{gathered} \text{Maximize } \sum_{u \in U} \pi_u + \sum_{w \in W} \pi_w\\ \begin{aligned} \text{s.t.}\ \pi_u + \pi_w &\le c_{u,w} && \forall (u,w) \in E\\ \pi_w &\le 0 && \forall w \in W. \end{aligned} \end{gathered}\tag{7.8}\]

With the same substitution, the complementary slackness condition (7.7) becomes

\[\pi_u + \pi_w = c_{u,w} \quad \text{or} \quad x_{u,w} = 0.\]

We can consider \(\pi\) to be a function assigning a potential \(\pi_v\) to every vertex of \(G\). Since we have the constraint \(\pi_u + \pi_w \le c_{u,w}\) for every edge \((u,w) \in E\), it is natural to call an edge tight if \(\pi_u + \pi_w = c_{u,w}\). Since our primal LP encodes that the subset of edges \(M \subseteq E\) we want to find is a perfect matching, we can interpret the complementary slackness condition as: Find a perfect matching \(M \subseteq E\) and a potential function \(\pi\) such that \(M\) contains only tight edges.

Lemma 7.17: A perfect matching \(M\) in a bipartite graph \(G = (U, W, E)\) is a minimum-weight perfect matching if and only if there exists a potential function \(\pi\) such that every edge in \(M\) is tight.

This lemma does in fact hold for any graph \(G\), not only for bipartite graphs, and it has an extremely short combinatorial proof. I chose to arrive at Lemma 7.17 in a seemingly roundabout fashion, via LP duality and complementary slackness, because it makes it obvious that the Hungarian Algorithm, discussed next, is an application of the primal-dual schema. Without the derivation of Lemma 7.17 via LP duality, the introduction of a potential function \(\pi\) to help us pick the edges in \(M\) and the adjustments to \(\pi\) made by the algorithm would seem more "magical".