Hungarian method

Abstract view

Algorithmic problem: Maximum-weight matching in complete bipartite graphs [math]\displaystyle{ G=(V_1\dot\cup V_2,E) }[/math] with [math]\displaystyle{ |V_1|=|V_2| }[/math].

Type of algorithm: loop.

Auxiliary data:

1. A real number [math]\displaystyle{ x(v) }[/math] for each node [math]\displaystyle{ v\in V_1 }[/math].
2. A real number [math]\displaystyle{ y(w) }[/math] for each node [math]\displaystyle{ w\in V_2 }[/math].

Invariant:

1. [math]\displaystyle{ M }[/math] is a matching in [math]\displaystyle{ G }[/math].
2. For each edge [math]\displaystyle{ e=\{v,w\}\in M }[/math], where [math]\displaystyle{ v\in V_1 }[/math] and [math]\displaystyle{ w\in V_2 }[/math], it is [math]\displaystyle{ c(e)\leq x(v)+y(w) }[/math].

Variant:

Break condition: For each edge [math]\displaystyle{ e=\{v,w\} in M }[/math], where [math]\displaystyle{ v\in V_1 }[/math] and [math]\displaystyle{ w\in V_2 }[/math], it is [math]\displaystyle{ c(e)=x(v)+y(w) }[/math].

Induction basis

1. initialize [math]\displaystyle{ M }[/math] to be a feasible matching, for example, the empty matching.
2. Initialize all [math]\displaystyle{ x }[/math] and [math]\displaystyle{ y }[/math] values such that the invariant is fulfilled, for example:
   1. [math]\displaystyle{ x(v):=\max\{c(\{v,w\})|w\in V_2\} }[/math] for all [math]\displaystyle{ v\in V_1 }[/math].
   2. [math]\displaystyle{ y(w):=0 }[/math] for all [math]\displaystyle{ w\in V_2 }[/math],

Induction step

Notation:

1. For a node [math]\displaystyle{ v\in V_1 }[/math]: [math]\displaystyle{ N(v):=\{w\in V_2|c(\{v,w\})=x(v)+y(w)\} }[/math], the neighbors of [math]\displaystyle{ v }[/math].
2. For a set [math]\displaystyle{ S\subseteq V_1 }[/math]: [math]\displaystyle{ N(S):=\bigcup_{v\in S}N(v) }[/math].

Abstract view:

1. Let [math]\displaystyle{ G'=(V,E') }[/math] be the subgraph of [math]\displaystyle{ G }[/math] where [math]\displaystyle{ E' }[/math] comprises all edges [math]\displaystyle{ e=\{v,w\}\in E }[/math] ([math]\displaystyle{ v\in V_1 }[/math], [math]\displaystyle{ w\in V_2 }[/math]) such that [math]\displaystyle{ c(e)=x(v)+y(w) }[/math].
2. Try to find an augmenting path in [math]\displaystyle{ G' }[/math] with respect to [math]\displaystyle{ M }[/math].
3. If step 2 succeeds, augment [math]\displaystyle{ M }[/math] along this path.
4. Otherwise:
   1. Choose some exposed node [math]\displaystyle{ v\in V_1 }[/math].
   2. Initialize two sets, [math]\displaystyle{ S:=\{v\} }[/math], [math]\displaystyle{ T:=\emptyset }[/math].
   3. While [math]\displaystyle{ T\subsetneq N(S) }[/math]:
      1. Let [math]\displaystyle{ w\in N(s)\setminus T }[/math]..
      2. Let [math]\displaystyle{ \{u,w\} }[/math] be the unique edge incident to [math]\displaystyle{ w }[/math] that is in [math]\displaystyle{ M }[/math].
      3. Insert [math]\displaystyle{ w }[/math] in [math]\displaystyle{ T }[/math] and [math]\displaystyle{ u }[/math] in [math]\displaystyle{ S }[/math].
   4. Set \delta:=\min\{c(\{u,w\}-x(u)-y(w)|u\in S,w\in V_2\setminus T\}</math>.
   5. For all [math]\displaystyle{ v\in V_1 }[/math], decrease [math]\displaystyle{ x(v) }[/math] by [math]\displaystyle{ \delta }[/math].
   6. For all [math]\displaystyle{ w\in V_2 }[/math], decrease [math]\displaystyle{ x(v) }[/math] by [math]\displaystyle{ \delta }[/math].

Remark: Steps 2 and 4 can be folded into one loop, which breaks if [math]\displaystyle{ N(S)=T }[/math] or an exposed node (and thus an augmenting path) is found.

Proof: Note that [math]\displaystyle{ is indeed matched because, otherwise, step ?? had found an augmenting path, which had rather been found in step 2. == Correctness == Termination of the main loop will follow from the complexity considerations below. Let \lt math\gt M }[/math] be a perfect matching and [math]\displaystyle{ x }[/math] and [math]\displaystyle{ y }[/math] be given such that [math]\displaystyle{ c(e)=x(v)+y(w) }[/math] for all [math]\displaystyle{ e=\{v,w\}\in M }[/math], where [math]\displaystyle{ v\in V_1 }[/math] and [math]\displaystyle{ w\in V_2 }[/math]. Let [math]\displaystyle{ M' }[/math] be another matching. Due to the invariant, it is

[math]\displaystyle{ c(M)=\sum_{v\in V_1,w\in V_2\atop e=\{v,w\}\in M}c(e)=\sum_{v\in V_1}x(v)+\sum_{w\in V_2}y(w)\geq\sum_{v\in V_1,w\in V_2\atop e=\{v,w\}\in M'}c(e) }[/math].

Therefore, [math]\displaystyle{ M }[/math] is maximal.

Remark: In particular, the following equivalence is proved: A perfect matching [math]\displaystyle{ M }[/math] has maximum weight if, and only if, there are [math]\displaystyle{ x }[/math] and [math]\displaystyle{ y }[/math] such that [math]\displaystyle{ c(e)=x(v)+y(w) }[/math] for all [math]\displaystyle{ e=\{v,w\}\in M }[/math].