# The Hungarian Algorithm

In reading the proof of the Hungarian algorithm for the assignment problem in a weighted bigraph, I could not understand why the algorithm terminates. In the algorithm we choose a cover (namely labels for the vertices of the bigraph: $u_1\cdots u_n$, $v_1,\cdots v_n$ with $u_i+v_j\ge$weight of an edge $x_iy_j\forall i,j$) and keep adjusting it until the equality subgraph (the spanning subgraph of $K_{n,n}$ whose edges are pairs $x_iy_j$ such that $u_i+v_j=$weight of $x_iy_j$) has a perfect matching. My question is after each adjustment, why does the cost of the cover $\sum(u_i+v_i)$ reduce?

(We assume the weights are all integers).

Thanks.

-

Let the two sets of vertices be $X$ and $Y$. If the equality subgraph does not have a perfect matching, it must violate Hall’s marriage condition, so there is some $X'\subseteq X$ adjacent to fewer than $|X'|$ vertices in $Y$. Let $Y'$ be the set of vertices in $Y$ adjacent to $X'$ in the equality subgraph. The adjustment to the cover consists in replacing $u_k$ by $u_k-\alpha$ for each $x_k\in X'$ and $v_k$ by $v_k+\alpha$ for each $y_k\in Y'$, where $\alpha=\min\{u_k+v_j-\operatorname{wt}(x_ky_j):u_k\in X'\text{ and }y_j\in Y'\}$. The net change in the cost of the cover is therefore $\left(-|U'|+|V'|\right)\alpha<0$, and the cost of the new cover is therefore less than the cost of the old.