# maximal bipartite matching algorithm

The maximal bipartite matching algorithm is similar some ways to the Ford-Fulkerson algorithm for network flow. This is not a coincidence; network flows and matchings are closely related. This algorithm, however, avoids some of the overhead associated with finding network flow.

The basic idea behind this algorithm is as follows:

1. 1.

Start with some (not necessarily maximal) matching $M$.

2. 2.

Find a path that alternates with an edge $e_{1}\not\in M$, followed by an edge $e_{2}\in M$, and so on, ending with some edge $e_{f}\not\in M$.

3. 3.

For each edge $e$ in the path, add $e$ to $M$ if $e\not\in M$ or remove $e$ from $M$ if $e\in M$. Note that this must increase $|M|$ by $1$.

4. 4.

Repeat until we can no longer augment the matching in this manner.

The algorithm employs a clever labeling trick to find these paths and to ensure that the set of edges chosen remains a valid matching.

The algorithm as described here uses the matrix form of a bipartite graph. Translating the matching from a matrix to a graph is straightforward.

There are two phases to this algorithm: labeling and flipping.

## Labeling

We begin with a matrix with $R$ rows and $C$ columns containing $0$s, $1$s, and $1*$s, where a $1*$ indicates in edge in the matching and a $1$ indicates an edge not in the matching. Number the columns $1\dots C$ and number the rows $1\dots R$.

Start by labeling each column that contains no $1*$s with the symbol $\#$.

Now we scan the columns. Scan each column $i$ that has been labelled but not scanned. Find each $1$ in column $i$ that is in an unlabelled row; label this row $i$. Mark column $i$ as scanned.

Next, we scan the rows. Scan each row $j$ that has been labelled but not scanned. Find the first $1*$ in row $j$. Label the column in which it appears $j$, and mark row $j$ as scanned. If there is no $1*$ in row $j$, proceed to the flipping phase.

Otherwise, go back to column scanning. Continue scanning and labelling until there are no labelled, unscanned rows or columns; at that point, the set of $1*$s is a maximal matching.

## Flipping

We enter the flip phase when we scan some row $j$ that contains no $1*$. This row must have some label $c$, and in column $c$, row $j$ of the matrix, there must be a $1$; change this to a $1*$.

Now consider column $c$; it has some label $r$. If $r$ is $\#$, clear all the labels and mark all rows and columns unscanned, and begin the labeling phase again. Otherwise, change the $1*$ at column $c$, row $r$ to a $1$.

Move on to row $r$ and scan this row.

## Notes

The algorithm must begin with some matching; we may begin with the empty set (or a single edge), since that is always a matching. However, each iteration through the process increases the size of the matching by exactly one. Therefore, we can make a simple optimization by starting with a larger matching. A naïve greedy algorithm can quickly choose a valid matching that is usually close to the size of the maximal matching; we may initalize our matrix with that matching to give the procedure a head start.

Title maximal bipartite matching algorithm MaximalBipartiteMatchingAlgorithm 2013-03-22 12:40:11 2013-03-22 12:40:11 mathcam (2727) mathcam (2727) 7 mathcam (2727) Algorithm msc 05C70