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. Choose some exposed node [math]\displaystyle{ v\in V_1 }[/math].
3. Initialize two sets, [math]\displaystyle{ S:=\{v\} }[/math], [math]\displaystyle{ T:=\emptyset }[/math].
4. While [math]\displaystyle{ T\subsetneq N(S) }[/math]

Remark: separated into two phases:

1. Try to find an augmenting path in [math]\displaystyle{ G' }[/math] with respect to [math]\displaystyle{ M }[/math].
2. If step 2 succeeds, augment [math]\displaystyle{ M }[/math] along this path.
3. Otherwise:

Correctness

Termination of the main loop will follow from the complexity considerations below. Let [math]\displaystyle{ 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].