4
$\begingroup$

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.

2 Answers 2

4

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.

This PDF has a presentation that I think is slightly different from the one that you have in mind; it arrives at the optimality by a different route that may be easier to follow, especially with the nice example at the end.

1

Let $\mathrm{M}$ be a maximum matching in the equality subgraph. According to König's theorem, we can find a vertex cover $C$ such that $\mathrm{|M|}=|C|$. We Call $R$ the set $C\cap X$, and $T$ the set $C\cap Y$. Now, either $\mathrm{M}$ is a perfect matching, which means the algorithm should stop and return our current labelling as optimal, or $X$ is not saturated by $\mathrm{M}$. In that case, we adjust the weighted cover : We define $\epsilon = \min\{(u_i+v_j-w(x_iy_j):x_i\notin R, y_j \notin T\}$, and we substract $\epsilon$ to $u_i$ for each $x_i \notin R$, and we add $\epsilon$ to each $y_j$ for each $y_j \in T$. The cost of the cover changes by $(|T| - |X\setminus R|)\epsilon$. This change is strictly negative because $|R|+|T|=|\mathrm{M}|\lt |X| \Rightarrow |T| \lt |X|-|R| \Rightarrow |T| \lt |X \setminus R|$. Since we assumed the integrality of the labels, it ensures that the algorithm terminates in finitely many steps.