Kuhn's algorithm — maximum matching in a bipartite graph

Given a bipartite graph $G=(V,E)$ with parts:

left: $A$ , $|A|=n_1$
right: $B$ ,

Up next

Kőnig's theorem

B

|B|=n_2

It is required to find a maximum matching — the maximum set of edges that do not share common vertices.

Idea of the Kuhn algorithm

The Kuhn algorithm is a direct application of Berge's theorem:

A matching is maximum ⇔ there are no augmenting paths in the graph.

The algorithm works as follows:

start with an empty matching
for each vertex of the left part, try to find an augmenting path
if found — augment the matching
when there are no paths — the matching is maximum

Augmenting path

An augmenting path is a path that:

starts at a free vertex of the left part
ends at a free vertex of the right part
edges alternate: not in the matching / in the matching

After alternating edges along the path, the size of the matching increases by 1.

Finding an augmenting path

For a vertex $v$ of the left part:

iterate over all edges $(v,to)$
if $to$ is free → found a path
otherwise try to recursively rearrange through its mate

That is:

if $to$ is not occupied
or it is possible to free $to$ through its current mate

→ connect $v$ with $to$

Algorithm

For all $v \in A$ :

if $v$ is free
run DFS to search for a path

Complexity

Each DFS — $O(m)$
Run up to $n_1$ times:

O(n_1 m)

In the worst case:

O(n^3)

Important:

the algorithm is run only from the left part
therefore it is beneficial to choose the smaller part on the left

Implementation

int n, k;
vector<vector<int>> g;
vector<int> mt;
vector<char> used;

bool try_kuhn(int v) {
    if (used[v]) return false;
    used[v] = true;

    for (int to : g[v]) {
        if (mt[to] == -1 || try_kuhn(mt[to])) {
            mt[to] = v;
            return true;
        }
    }
    return false;
}

int main() {
    // reading the graph

    mt.assign(k, -1);

    for (int v = 0; v < n; v++) {
        used.assign(n, false);
        try_kuhn(v);
    }

    // output the matching
    for (int i = 0; i < k; i++) {
        if (mt[i] != -1) {
            cout << mt[i] + 1 << " " << i + 1 << "\n";
        }
    }
}