Perfect Matching

Abstract

This is pseudocode for Perfect Matching in Bipartite Graphs, adapted from the paperback edition of A Gentle Introduction to Optimization, B. Guerin et al. This is used as a subroutine to find any perfect matching on a subgraph of the larger bipartite graph in the Hungarian Algorithm, whose goal is to find a minimum weight perfect matching.

The operator $\mathrm{\Delta }$ is essentially an exclusive OR (XOR) of the two sets:

$M\mathrm{\Delta }P=(M\cup P)\setminus (M\cap P).$

(1)

Executed on an alternating paths of links included in versus excluded from the set and a second path including at leaast part of that first set, it has the behavior of flipping the ones included versus excluded.

I believe this algorithm as stated assumes that the input graph $H$ is connected.

.4

Perfect Matching

{ } 

InputInputOutputOutput Bipartite graph $H=(V,E)$ with bipartition $U$,$W$ where $|U|=|W|\ge 1$ A perfect matching $M$, or a deficient set $B$ $\subseteq$ $U$. $M:=\mathrm{\varnothing }$
$T:=(\{r\},\mathrm{\varnothing }$) where $r\in U$ is any $M$-exposed vertex
(1) $\exists$ $uv$ where $u$ $\in$ $B(T)$ and $v\notin V(T)$ $v$ is $M$-exposed $P:=T_{ru}\cup \{uv\}$
$M:=M\mathrm{\Delta }P$
$M$ is a perfect matchingstop $T:=(\{r\},\mathrm{\varnothing })$ where $r\in \cup$ is any $M$-exposed vertex. Let $w\in V$ where $vw\in M$
$T:=(V(T)\cup \{v,w\},E(T)\cup \{uv,vw\})$ stop $B(T)\subseteq U$ is a deficient set