The Hungarian algorithm: Kuhn-Munkres theorem

The Kuhn-Munkres theorem:

Given a bipartite graph with w(e) on edges, find a matching with maximum weight.

Simplified assumption, let the graph be bipartite complete, missing edges can be taken as w(e)=0.

Then we can assume optimal matching is perfect, that is, if |L|=|R|=n, then the matching M is of size n. the reason is that we can always add some edge if not perfect, and a complete bipartite graph must have a perfect matching.

Now we look for a feasible labeling on vertex, called slack, s(v), such that
s(x) + s(y) >= w(e) for e=(x,y). This ensures that sum of all s(v) is an upper bound on opt matching. Now we seek a feasible labeling and a perfect matching on the admissible edge graph, an edge is admissible if s(x) + s(y) = w(e). This prefect matching is necessarily optimal.

The algorithm starts with a feasible labeling, each v in L has s(v)=w(e), each v in R has s(v)=0, and an empty matching M.

Now find a free vertex in L, call it x0, we then look for a way to extend the matching by one more edge.

If x0 leads to an alternating path in E(admissible), then we augment. Otherwise we end up with a subset L' and R' such that L' is contained by R'. We then lower s(v) in L' and increase s(v) in R'. This keeps edges admissible if they are admissible before, and it will give us at least one more admissible edge to augment the matching.

Time complexity is O(|V|^3).

Variantions:
- The above algorithm assumes all w(e)>=0, what if we are given some w(e) <0?
 Simply replace those w(e) by 0. The reason is that if those w(e) were not chosen in the solution, then we are good. If they do get included in the solution, they can only beat edges with w(e)=0, then we are fine as well since we can simply throw away the w(e) <0 that we get in the solution.

- How about finding minimum weight perfect matching?
We can use some large integer Z and replace each w(e) with Z - w(e). Now we look for maximum matching instead. Since the solution has to be a perfect matching, flip sign of w(e) does not change the optimal solution, although its value needs to be restored.

- Implementation

nodes: X = 0,1,...,N-1,
Y=N,...,2*N-1

slack[i]=0 for each i in Y
slack[j]= max w(i, j) among all i in Y
mate[i]=-1 for i in Y
mate[j]=-1 for j in X

ans=0
for i = 0 to N-1
    if mate[i]==-1 // i not matched yet
         clear vis[]
         while (update = augment(i) is false)
             // update slack[]
             delta = inf
             for each j in X that vis[j] is true
                   for each i in Y that vis[i] is false
                         checkmin(delta, w(i,j) - s[j] - s[i]) // how much s[j] can decrease,   
                                                      //notice that s[i] is not changed in this update
              for each j in X that vis[j] is true: slack[j] -= delta
              for each i in Y that vis[i] is true: slakc[i] +=delta
              clear vis[]
            // after enough update, i must reach all j in X, so an augment has to occur
            ans++ // each augment increase matching size by 1

function augment(vertex s): return true if augment
    if (vis[s]) return false;
    vis[s] = true;
    for each neighbor z of s // only edges with w(e) = slack[x] + slack[y]  eligible
          if (mate[z]==-1):
                  then mate[z] = s, mate[s]=z, return true
          if (augment(mate[z]) is true):
                  then mate[z]=s, mate[s]=z, return true
    return false

Observation: once a vertex is matched, it stays matched