Bipartite Matching

Bipartite Matching is the problem of finding the maximum matching in a bipartite graph.

Kuhn’s Algorithm (Hungarian Algorithm for Matching)

A simple augmenting path algorithm for maximum matching in $O(VE)$ time.

Implementation

class BipartiteMatching {
    int n, m;  // n = left size, m = right size
    vector<vector<int>> adj;  // adjacency list for left side
    vector<int> match;  // match[right_node] = left_node (or -1)
    vector<bool> used;
    bool dfs(int v) {
        for (int to : adj[v]) {
            if (!used[to]) {
                used[to] = true;
                if (match[to] == -1 || dfs(match[to])) {
                    match[to] = v;
                    return true;
                }
            }
        }
        return false;
    }
public:
    BipartiteMatching(int n, int m) : n(n), m(m), adj(n), match(m, -1), used(m) {}
    void addEdge(int u, int v) {
        adj[u].push_back(v);
    }
    int maxMatching() {
        int result = 0;
        for (int v = 0; v < n; v++) {
            fill(used.begin(), used.end(), false);
            if (dfs(v)) {
                result++;
            }
        }
        return result;
    }
    // Get the matching pairs (left, right)
    vector<pair<int, int>> getMatching() {
        vector<pair<int, int>> result;
        for (int i = 0; i < m; i++) {
            if (match[i] != -1) {
                result.push_back({match[i], i});
            }
        }
        return result;
    }
};

Hopcroft-Karp Algorithm

A faster algorithm for maximum matching in $O(E \sqrt{V})$ time.

Implementation

class HopcroftKarp {
    int n, m;
    vector<vector<int>> adj;
    vector<int> matchL, matchR;
    vector<int> dist;
    bool bfs() {
        queue<int> q;
        for (int u = 0; u < n; u++) {
            if (matchL[u] == -1) {
                dist[u] = 0;
                q.push(u);
            } else {
                dist[u] = INT_MAX;
            }
        }
        bool found = false;
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int v : adj[u]) {
                int next = matchR[v];
                if (next == -1) {
                    found = true;
                } else if (dist[next] == INT_MAX) {
                    dist[next] = dist[u] + 1;
                    q.push(next);
                }
            }
        }
        return found;
    }
    bool dfs(int u) {
        for (int v : adj[u]) {
            int next = matchR[v];
            if (next == -1 || (dist[next] == dist[u] + 1 && dfs(next))) {
                matchL[u] = v;
                matchR[v] = u;
                return true;
            }
        }
        dist[u] = INT_MAX;
        return false;
    }
public:
    HopcroftKarp(int n, int m) : n(n), m(m), adj(n), matchL(n, -1), matchR(m, -1), dist(n) {}
    void addEdge(int u, int v) {
        adj[u].push_back(v);
    }
    int maxMatching() {
        int result = 0;
        while (bfs()) {
            for (int u = 0; u < n; u++) {
                if (matchL[u] == -1 && dfs(u)) {
                    result++;
                }
            }
        }
        return result;
    }
    vector<pair<int, int>> getMatching() {
        vector<pair<int, int>> result;
        for (int u = 0; u < n; u++) {
            if (matchL[u] != -1) {
                result.push_back({u, matchL[u]});
            }
        }
        return result;
    }
};

Useful Theorems

Konig’s Theorem

In a bipartite graph:

$\text{Maximum Matching} = \text{Minimum Vertex Cover}$

Hall’s Theorem

A bipartite graph $G = (L \cup R, E)$ has a matching that saturates $L$ if and only if:

$|N(S)| \geq |S| \text{ for all } S \subseteq L$

where $N(S)$ is the set of neighbors of $S$.

Finding Minimum Vertex Cover

vector<int> minVertexCover() {
    // Run max matching first
    maxMatching();
    vector<bool> visitedL(n, false), visitedR(m, false);
    queue<int> q;
    for (int u = 0; u < n; u++) {
        if (matchL[u] == -1) {
            q.push(u);
            visitedL[u] = true;
        }
    }
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : adj[u]) {
            if (!visitedR[v]) {
                visitedR[v] = true;
                if (matchR[v] != -1 && !visitedL[matchR[v]]) {
                    visitedL[matchR[v]] = true;
                    q.push(matchR[v]);
                }
            }
        }
    }
    // Vertex cover: unvisited left + visited right
    vector<int> cover;
    for (int u = 0; u < n; u++) {
        if (!visitedL[u]) cover.push_back(u);  // left side
    }
    for (int v = 0; v < m; v++) {
        if (visitedR[v]) cover.push_back(n + v);  // right side
    }
    return cover;
}

Applications

• Job assignment
• Domino covering on grids
• Maximum independent set in bipartite graphs

$\text{Maximum Independent Set} = V - \text{Minimum Vertex Cover}$