[proofplan] We prove correctness by maintaining two invariants: the potentials remain feasible, and every edge of the current [matching](/page/Matching) is tight in the current equality graph. An augmentation along an [alternating path](/page/Alternating%20Path) increases the matching size while preserving tightness. If no augmenting path is currently visible, the Hungarian update preserves feasibility and all matched tight edges, while creating at least one new tight edge leaving the reachable row set. Hence a fixed search phase can enlarge the reachable column set only finitely many times before finding an augmenting path, and after $n$ augmentations the matching is [perfect](/page/Perfect%20Matching). Finally, dual feasibility and tightness of the perfect matching give optimality by [complementary slackness](/theorems/2559). [/proofplan] [step:Maintain feasibility and tightness at the start of each search phase] Let $M \subset R \times C$ denote the current [matching](/page/Matching), and let $u: R \to \mathbb{R}$ and $v: C \to \mathbb{R}$ denote the current potentials. Define the equality graph associated to $u$ and $v$ by \begin{align*} E(u,v) := \{(i,j) \in R \times C : u(i)+v(j)=c(i,j)\}. \end{align*} We maintain the following two invariants: $u(i)+v(j) \leq c(i,j)$ for every $(i,j) \in R \times C$, and $u(i)+v(j)=c(i,j)$ for every $(i,j) \in M$. The invariant holds initially because feasibility is assumed and $M_0=\varnothing$. Thus there are no matched edges whose tightness must be checked at the initial stage. [/step] [step:Augment along a tight alternating path without losing the invariant] Assume the maximal [alternating tree](/page/Alternating%20Tree) in the equality graph $E(u,v)$ reaches an unmatched column $j_0 \in C$. Let $i_0 \in R$ be the unmatched root row, and let $P$ be the [alternating path](/page/Alternating%20Path) in the tree from $i_0$ to $j_0$. We regard $P$ as its finite edge set when forming set operations. Since the tree lies in $E(u,v)$, every edge of $P$ is tight. Define the new matching by symmetric difference with the edge set of $P$: \begin{align*} M' := M \triangle P. \end{align*} Along $P$, unmatched edges become matched and matched edges become unmatched. Since $P$ begins at an unmatched row and ends at an unmatched column, this operation increases the number of matched edges by one: \begin{align*} |M'| = |M|+1. \end{align*} Every edge added to $M'$ lies on $P$, hence is tight. Every edge of $M$ not on $P$ remains in $M'$ and was tight by the invariant. Therefore every edge of $M'$ is tight, and the potentials have not changed, so feasibility is also preserved. [guided] Suppose the alternating tree reaches an unmatched column $j_0$. The tree was built inside the equality graph, so every edge used by the tree satisfies \begin{align*} u(i)+v(j)=c(i,j). \end{align*} Let $i_0$ be the unmatched root row. There is a unique tree path $P$ from $i_0$ to $j_0$, and this path alternates between edges outside $M$ and edges inside $M$. We define \begin{align*} M' := M \triangle P, \end{align*} where $M \triangle P$ means that edges of $P$ already in $M$ are removed and edges of $P$ not in $M$ are added. Because $P$ starts at an unmatched row and ends at an unmatched column, the path has one more unmatched edge than matched edge. Hence the symmetric-difference operation adds exactly one more edge than it removes, so \begin{align*} |M'|=|M|+1. \end{align*} We also need to check that $M'$ is still a matching. At each internal vertex of $P$, one incident matched edge is removed and one incident unmatched edge is added, so the vertex remains incident to exactly one matched edge after the operation. The two endpoints $i_0$ and $j_0$ were previously unmatched and each gains exactly one matched edge. Vertices outside $P$ are unchanged. Thus $M'$ is a matching. Finally, every newly added edge lies on $P$, and every edge of $P$ lies in the equality graph. Therefore every newly added edge is tight. Edges of $M$ that are not on $P$ remain tight by the induction invariant. Since the potentials are unchanged during augmentation, feasibility remains true for all pairs $(i,j) \in R \times C$. [/guided] [/step] [step:Use maximality of the alternating tree when no augmenting column is reached] Assume the current maximal [alternating tree](/page/Alternating%20Tree) does not reach an unmatched column. Let $S \subset R$ be the set of reachable rows and $T \subset C$ the set of reachable columns. First, every column in $T$ is matched. Indeed, if some $j \in T$ were unmatched, the alternating path from the root row to $j$ would be an augmenting path, contrary to the assumption of this case. Second, every equality edge from a row in $S$ enters $T$: \begin{align*} (i,j) \in E(u,v),\ i \in S \implies j \in T. \end{align*} If such a column $j$ were not in $T$, then the alternating tree could be enlarged by adding the tight edge $(i,j)$ from the reachable row $i$, contradicting maximality. Third, matched partners of reachable columns are reachable rows. If $j \in T$ and $(i,j) \in M$, then the alternating-tree construction includes the matched edge from $j$ back to $i$, so $i \in S$. Combining the previous two observations, every matched edge incident to $S$ has its column endpoint in $T$, and every matched edge incident to $T$ has its row endpoint in $S$. [/step] [step:Perform the Hungarian update while preserving feasibility] In the no-augmenting-column case, $S$ is nonempty because it contains the root row. Also $T \neq C$: since every column in $T$ is matched and the current matching is not perfect during a search phase, at least one column is unmatched and therefore not in $T$. Define the slack function $\sigma:S \times (C \setminus T) \to [0,\infty)$ by, for each $(i,j) \in S \times (C \setminus T)$, \begin{align*} \sigma(i,j) := c(i,j)-u(i)-v(j). \end{align*} By feasibility, $\sigma(i,j) \geq 0$. By maximality of the alternating tree, no edge from $S$ to $C \setminus T$ is tight, so $\sigma(i,j)>0$ for all $(i,j) \in S \times (C \setminus T)$. Since $S \times (C \setminus T)$ is finite and nonempty, the minimum \begin{align*} \delta := \min\{\sigma(i,j): i \in S,\ j \in C \setminus T\} \end{align*} exists and satisfies $\delta>0$. Define updated potentials $u':R \to \mathbb{R}$ and $v':C \to \mathbb{R}$ as follows. For $i \in S$, set \begin{align*} u'(i) := u(i)+\delta. \end{align*} For $i \in R \setminus S$, set \begin{align*} u'(i) := u(i). \end{align*} For $j \in T$, set \begin{align*} v'(j) := v(j)-\delta. \end{align*} For $j \in C \setminus T$, set \begin{align*} v'(j) := v(j). \end{align*} We check feasibility by cases. If $i \in S$ and $j \in T$, then \begin{align*} u'(i)+v'(j)=u(i)+\delta+v(j)-\delta=u(i)+v(j)\leq c(i,j). \end{align*} If $i \notin S$ and $j \notin T$, then \begin{align*} u'(i)+v'(j)=u(i)+v(j)\leq c(i,j). \end{align*} If $i \in S$ and $j \notin T$, then $\delta \leq \sigma(i,j)$ by definition of $\delta$, so \begin{align*} u'(i)+v'(j)=u(i)+\delta+v(j)\leq u(i)+v(j)+\sigma(i,j)=c(i,j). \end{align*} If $i \notin S$ and $j \in T$, then \begin{align*} u'(i)+v'(j)=u(i)+v(j)-\delta\leq u(i)+v(j)\leq c(i,j). \end{align*} Therefore $u'$ and $v'$ are feasible. Matched tight edges remain tight. Let $(i,j) \in M$. If $i \in S$, then the previous step gives $j \in T$, and the two potential changes cancel: \begin{align*} u'(i)+v'(j)=u(i)+v(j)=c(i,j). \end{align*} If $i \notin S$, then $j \notin T$; otherwise the matched partner of $j \in T$ would lie in $S$. Hence \begin{align*} u'(i)+v'(j)=u(i)+v(j)=c(i,j). \end{align*} Thus the invariant is preserved. [guided] The purpose of the potential update is to create new tight edges leaving the reachable rows, while not breaking feasibility. We first define the slack on the pairs that could possibly enlarge the tree. Let $\sigma:S \times (C \setminus T) \to [0,\infty)$ be the function defined by, for each $(i,j) \in S \times (C \setminus T)$, \begin{align*} \sigma(i,j) := c(i,j)-u(i)-v(j). \end{align*} Feasibility gives $\sigma(i,j)\geq 0$. In fact $\sigma(i,j)>0$ for all $i \in S$ and $j \in C \setminus T$, because if $\sigma(i,j)=0$, then $(i,j)$ would be an equality edge from a reachable row to a column not yet in the tree. The maximality of the alternating tree would then force $j$ to be reachable, contradicting $j \notin T$. The set $S \times (C \setminus T)$ is finite and nonempty. It is finite because $R$ and $C$ are finite. It is nonempty because $S$ contains the root row, and $C \setminus T$ is nonempty: every column in $T$ is matched, while the current matching is not yet perfect and therefore has some unmatched column. Hence the number \begin{align*} \delta := \min\{\sigma(i,j): i \in S,\ j \in C \setminus T\} \end{align*} is well-defined and positive. Now define $u':R \to \mathbb{R}$ and $v':C \to \mathbb{R}$ by four rules. For $i \in S$, set \begin{align*} u'(i) := u(i)+\delta. \end{align*} For $i \in R \setminus S$, set \begin{align*} u'(i) := u(i). \end{align*} For $j \in T$, set \begin{align*} v'(j) := v(j)-\delta. \end{align*} For $j \in C \setminus T$, set \begin{align*} v'(j) := v(j). \end{align*} We verify feasibility for every pair $(i,j) \in R \times C$. If $i \in S$ and $j \in T$, then the row potential increases by $\delta$ and the column potential decreases by $\delta$, so the sum is unchanged: \begin{align*} u'(i)+v'(j)=u(i)+v(j)\leq c(i,j). \end{align*} If $i \notin S$ and $j \notin T$, neither potential changes, so \begin{align*} u'(i)+v'(j)=u(i)+v(j)\leq c(i,j). \end{align*} If $i \in S$ and $j \notin T$, then only the row potential increases. The definition of $\delta$ gives \begin{align*} \delta \leq c(i,j)-u(i)-v(j), \end{align*} and therefore \begin{align*} u'(i)+v'(j)=u(i)+\delta+v(j)\leq c(i,j). \end{align*} If $i \notin S$ and $j \in T$, then only the column potential decreases, so \begin{align*} u'(i)+v'(j)=u(i)+v(j)-\delta\leq u(i)+v(j)\leq c(i,j). \end{align*} Thus feasibility survives the update. It remains to check that the current matching remains inside the equality graph. Let $(i,j)\in M$. If $i\in S$, then the matched edge from $i$ is tight, so maximality of the reachable column set gives $j\in T$. The changes cancel: \begin{align*} u'(i)+v'(j)=u(i)+\delta+v(j)-\delta=u(i)+v(j)=c(i,j). \end{align*} If $i\notin S$, then $j\notin T$; otherwise the alternating-tree rule would follow the matched edge from $j$ back to $i$ and include $i$ in $S$. Hence neither endpoint changes, and \begin{align*} u'(i)+v'(j)=u(i)+v(j)=c(i,j). \end{align*} So every matched edge remains tight after the Hungarian update. [/guided] [/step] [step:Create a new tight edge and force progress within the same phase] By definition of $\delta$, there exists at least one pair $(i_1,j_1) \in S \times (C \setminus T)$ such that \begin{align*} \delta = c(i_1,j_1)-u(i_1)-v(j_1). \end{align*} For this pair, \begin{align*} u'(i_1)+v'(j_1)=u(i_1)+\delta+v(j_1)=c(i_1,j_1), \end{align*} so $(i_1,j_1)$ is a new equality edge from $S$ to $C \setminus T$. Continue the same search phase in the updated equality graph. The previously reachable part of the alternating tree remains valid: every old equality edge between $S$ and $T$ has unchanged potential sum, and every matched edge remains tight by the preceding step. Thus every vertex that was reachable before the update is still reachable after the update. If $j_1$ is unmatched, then the old tight path from the root to $i_1$ followed by the new tight edge $(i_1,j_1)$ is an augmenting path. If $j_1$ is matched, then $j_1$ enters the reachable column set, and its matched row enters the reachable row set by the alternating-tree rule. Therefore, unless an augmentation occurs immediately, the reachable column set $T$ strictly increases. [/step] [step:Terminate after finitely many potential updates and augmentations] Fix one search phase, beginning with a matching $M$ of size $k<n$. During this phase, every time a potential update is performed and no augmenting path is found immediately afterward, the reachable column set $T$ strictly increases. Since $T \subset C$ and $|C|=n$, this can happen at most $n$ times in the phase. Therefore each search phase ends after finitely many potential updates with an augmenting path, and the next augmentation increases the matching size by one. The matching size starts at $0$ and increases by one after each completed phase. Since a matching in $R \times C$ has size at most $n$, after exactly $n$ augmentations the algorithm reaches a matching $M_*$ with \begin{align*} |M_*|=n. \end{align*} Such a matching covers all rows and all columns, so $M_*$ is [perfect](/page/Perfect%20Matching). By the maintained invariant, $M_*$ is contained in the final equality graph. [/step] [step:Use dual feasibility and tightness to prove minimum cost] Let $u_*:R \to \mathbb{R}$ and $v_*:C \to \mathbb{R}$ be the final feasible potentials, and let $M_*$ be the final perfect matching. Since every edge of $M_*$ is tight, \begin{align*} \sum_{(i,j)\in M_*} c(i,j) = \sum_{(i,j)\in M_*} \bigl(u_*(i)+v_*(j)\bigr). \end{align*} Since $M_*$ is perfect, each row and each column appears exactly once, so \begin{align*} \sum_{(i,j)\in M_*} \bigl(u_*(i)+v_*(j)\bigr) = \sum_{i\in R} u_*(i)+\sum_{j\in C} v_*(j). \end{align*} Now let $N$ be any perfect matching in $R \times C$. Feasibility of $u_*,v_*$ gives \begin{align*} u_*(i)+v_*(j)\leq c(i,j) \end{align*} for every $(i,j)\in N$. Summing over $N$ and using that $N$ is perfect gives \begin{align*} \sum_{i\in R} u_*(i)+\sum_{j\in C} v_*(j) = \sum_{(i,j)\in N}\bigl(u_*(i)+v_*(j)\bigr). \end{align*} Feasibility on each edge of $N$ then gives \begin{align*} \sum_{(i,j)\in N}\bigl(u_*(i)+v_*(j)\bigr) \leq \sum_{(i,j)\in N} c(i,j). \end{align*} Combining the two displayed identities gives \begin{align*} \sum_{(i,j)\in M_*} c(i,j) \leq \sum_{(i,j)\in N} c(i,j) \end{align*} for every perfect matching $N$. Hence $M_*$ is a minimum-cost assignment. This completes the proof. [/step]