Minimum Cost Perfect Matching

Abstract

This is pseudocode for the Hungarian Algorithm for Minimum Cost Perfect Matching in Bipartite Graphs, adapted from the paperback edition of A Gentle Introduction to Optimization, B. Guerin et al. This finds subgraphs of the original bipartite graph (which is often a complete bipartite graph), and uses the Perfect Matching algorithm as a subroutine to figure out if there is a perfect matching, in which case we are done.

.5

$N_H(S)$ is the set of neighbors of the set $S$ on the graph $H$. One thing I do not like about this particular pseudocode is that the interface with the perfect matching subroutine is imprecise, and this algorithm depends on side effects from that subroutine. The subroutine might return (a) a new (larger) matching $M$, (b) a new (larger) tree $T$, or (c) a deficient set for that particular graph $H$.

Minimum cost perfect matching in bipartite graphs (fast version)

{ } 

InputInputOutputOutputDodoWhileBipartite graph $G=(V,E)$ with bipartition $U,W$ where $|U|=|W|\ge 1$ A minimum cost perfect matching $M$ or a deficient set $S$ $M:=\mathrm{\varnothing }$
$T:=(\{r\},\mathrm{\varnothing })$ where $r\in U$ is any $M$-exposed vertex
$\overrightarrow{y_v}:=\frac{1}{2}min\left\{c_e:e\in E\right\}\text{, for all }v\in V$

(1) Construct graph $H$ (a subset of the original graph $G$)
with vertices $V$ and edges {$uv$ $\in$ $E$ : $c_{uv}$ = $\overrightarrow{y_u}$ + $\overrightarrow{y_v}\}$
Invoke the subroutine (Algo. 3.4) with $H$,$M$, and $T$

outcome (a) of subroutine occurs $M$ is a perfect matching of $H$ stop ($M$ is minimum cost perfect matching of $G$) outcome (c) of subroutine occurs Let $S:=B(T)$
all edges of $G$ with an endpoint in $S$ have an endpoint in $N_H(S)$ stop ($G$ has no perfect matching) Otherwise, adjust the costs to create a new zero, and loop $ϵ=min\{c_{uv}-\overrightarrow{y_u}-\overrightarrow{y_v}:u\in S,v\notin V(T)\}$

$$\overrightarrow{y_v}:=\{\begin{array}{cc}\overrightarrow{y_v}+ϵ\text{ for }v\in S\hfill & \\ \overrightarrow{y_v}-ϵ\text{ for }v\in N_H(S)\hfill & \\ \overrightarrow{y_v}\text{ otherwise }\hfill & \end{array}$$

(1)

outcome (b) of subroutine occurs Just loop again with augmented path