## Hungarian algorithm, take 1

Hungarian algorithm is an efficient procedure to find a maximum weight matching in a bipartite graph $\Gamma=(V_1\cup V_2,E)$ with parts $V_1$ and $V_2$ and a weight function $w:E\to\mathbb{R}_+.$ Usually it is described in terms of potential functions on $V=V_1\cup V_2,$ and looks quite mysterious, as it hides the origin of the procedure, that is a variation of the augmenting path method for finding a maximum (unweighted) matching in $\Gamma.$ Here we describe this point of view.

Let $M$ be a matching of maximum weight $w(M)$ among all matchings of size $|M|.$ If $M$ is a maximum (unweighted) matching then we are done.

Otherwise, we construct a bipartite digraph $D=(V,A)$ by orienting all the edges in $M$ from $V_2$ to $V_1,$ and the remaining edges $E\setminus M$ in the opposite direction. We also construct the length function $\ell: A\to\mathbb{R}$ by setting $\ell(a)=w(a)$ for all $a\in M,$ and $\ell(a)=-w(a)$ for all $a\in A\setminus M.$ Observe that there no negative length (directed) cycles in $D$. Indeed, any directed cycle $C$ in $D$ contains equally many edges in $C\cap M$ from $M$ and in $C\setminus M.$ Note that $\ell(C)<0$ would mean that $w(C\cap M)< w(C\setminus M),$ and so $w(M)$ is not maximum among all matchings of size $|M|,$ as $w(C\triangle M)> w(M),$ whereas $|C\triangle M|=|M|.$

Let $V_1^M$ and $V_2^M$ be subsets of $V_1,$ resp. $V_2$ that are unsaturated by $M.$ We find (say, using the Bellman-Ford algorithm) a minimum length directed path $P$ between $V_1^M$ and $V_2^M.$ By construction of $D,$ $P$ is an augmenting path for $M.$ So $M'=M\triangle P$ is a matching satisfying $|M'|=|M|+1.$

Claim: $w(M')$ is maximum among all matchings of size $|M'|.$

We’ll prove this claim below. For now, we remark that it is obvious that this procedure, repeated with $M'$ taking place of $M,$ will find matchings of maximum weight among all matchings of size $1,2,3,\dots$ In the end it remains to select among these at most $\min(|V_1|,|V_2|)$ matchings one with maximum weight.

Now let us prove the claim. It certainly holds for $|M'|=1,$ as the procedure will select a maximum weight edge in $E$ and $M'$ will consist of this edge. So we can assume $|M'|\geq 2.$ Let $N$ be a matching of size $|M'|,$ and of maximum weight. We need to show that $w(N)\leq w(M').$ As $|N|=|M|+1,$ in the subgraph $N\cup M$ there
exists a connected component $Q$ that is a $M-$augmenting path $Q.$
But $P$ is a shortest $M-$augmenting path, so $\ell(Q)\geq\ell(P).$
On the other hand, $N\triangle Q$ is a matching of size $|M|,$ and so $w(N\triangle Q)\leq w(M),$ by induction. Now $w(N)=w(N\triangle Q)-\ell(Q)\leq w(M)-\ell(Q)\leq w(M)-\ell(P)=w(M'),$ as claimed. QED.

As described, we need to do less that $n=|V|$ loops of this procedure. In each loop, the Bellman-Ford dominates the complexity, so in total we need $O(n^2|E|)$ operations. In fact, we can stop as soon as we reached the situation when $w(M')\leq w(M).$

Let a matching $M$ have maximum $w(M)$ among matchings of size $|M|,$ and any matching $M'$ of size $|M'|=|M|+1$ satisfy $w(M')\leq w(M).$ Then $w(N)\leq w(M)$ for any matching $N$ of size bigger than $|M|.$

Proof. Suppose $N$ be a matching contradicting the claim, minimal w.r.t. $|N\triangle M|.$ Let $D$ be the digraph constructed from $\Gamma,$ $w,$ and $M$ as above. The connected components of $|N\triangle M|$ induce oriented cycles and directed paths on $D.$ Each such component will have a nonnegative total length, as neither there can be a negative length cycle in $D$ (see above) nor can there be a negative length $M$-augmenting path (otherwise we can construct $M'$). But this implies that $w(M)\geq w(N),$ contradiction. QED.

In particular, the complexity above can be improved to $O(n|M||E|).$