Maximum bipartite matching

Lesson · 11 min read · Graphs · Bipartite matching

Pair applicants with jobs so that as many as possible are placed: a maximum flow with every capacity 1, or a short augmenting-path search.

The problem

Four applicants, four jobs, and a list of which applicant is qualified for which job. Each job takes one person and each person takes one job. How many applicants can be placed? A set of pairs with no applicant or job used twice is a matching; the largest is a maximum matching.

An edge means the applicant is qualified for the job.

Assigning greedily can strand people: give J1 to A1 first and A2 may have nothing left later. As with flow, the cure is to let later choices move earlier ones.

Matching as maximum flow

Add a source joined to every applicant and a sink joined from every job, and give every edge capacity 1. An integral flow of value k picks k applicant–job edges with no applicant or job used twice, and the reverse is true too, so the maximum flow is the size of the maximum matching.

Every edge has capacity 1. The flow algorithm's reverse edges are exactly "move this applicant to another job".

Augmenting paths directly

Running a full flow algorithm is not necessary. The same idea, written for a bipartite graph, is short: for each applicant, look for a job that is free, or whose current holder can be moved to another job they qualify for, recursively. Each success is an augmenting path that alternates between unmatched and matched edges and adds one pair.

Augmenting-path matching (Kuhn)

tryAssign(a, seen)

For each job j that applicant a qualifies for, not yet in seen: add j to seen.
If j is free, or tryAssign(holder of j, seen) succeeds, give j to a and return true.
Return false.

maxMatching

For each applicant a: clear seen and call tryAssign(a, seen); count the successes.

Applicants are placed one at a time; when a job is taken, its holder is asked to move.

Step 1 / 4

matched1
A1: augmenting path A1–J1. J1 was free. 1 matched.
Step 2 / 4

matched2
A2: augmenting path A2–J1, A1–J2. To make room, A1 moves from J1 to J2. 2 matched.
Step 3 / 4

matched3
A3: augmenting path A3–J2, A1–J1, A2–J3. To make room, A1 moves from J2 to J1; A2 moves from J1 to J3. 3 matched.
Step 4 / 4

matched4
A4: augmenting path A4–J4. J4 was free. 4 matched. No more augmenting paths: the maximum matching has 4 pairs.

current matchingaugmenting path just usedcould not be placed

Implementation

The problem at the end of this module, with qualifications given as a 0/1 matrix:

import sys

def max_matching(matrix):
    sys.setrecursionlimit(10000)
    n, m = len(matrix), len(matrix[0])
    holder = [-1] * m                     # holder[j]: applicant currently in job j

    def try_assign(a, tried):
        for j in range(m):
            if matrix[a][j] and not tried[j]:
                tried[j] = True
                if holder[j] == -1 or try_assign(holder[j], tried):
                    holder[j] = a         # augmenting path found: a takes job j
                    return True
        return False

    return sum(1 for a in range(n) if try_assign(a, [False] * m))

#include <functional>
#include <vector>

int solve(const std::vector<std::vector<int>>& matrix) {
    const int n = matrix.size(), m = matrix[0].size();
    std::vector<int> holder(m, -1);              // applicant in each job
    std::vector<bool> tried;
    std::function<bool(int)> tryAssign = [&](int a) {
        for (int j = 0; j < m; ++j) {
            if (!matrix[a][j] || tried[j]) continue;
            tried[j] = true;
            if (holder[j] == -1 || tryAssign(holder[j])) { holder[j] = a; return true; }
        }
        return false;
    };
    int placed = 0;
    for (int a = 0; a < n; ++a) {
        tried.assign(m, false);                  // a fresh search per applicant
        if (tryAssign(a)) ++placed;
    }
    return placed;
}

class Solution {
    private int[][] matrix;
    private int[] holder;
    private boolean[] tried;

    private boolean tryAssign(int a) {
        for (int j = 0; j < holder.length; j++) {
            if (matrix[a][j] == 0 || tried[j]) continue;
            tried[j] = true;
            if (holder[j] == -1 || tryAssign(holder[j])) { holder[j] = a; return true; }
        }
        return false;
    }

    public int maxMatching(int[][] matrix) {
        this.matrix = matrix;
        holder = new int[matrix[0].length];
        java.util.Arrays.fill(holder, -1);           // applicant in each job
        int placed = 0;
        for (int a = 0; a < matrix.length; a++) {
            tried = new boolean[holder.length];      // a fresh search per applicant
            if (tryAssign(a)) placed++;
        }
        return placed;
    }
}

function maxMatching(matrix) {
  const n = matrix.length, m = matrix[0].length;
  const holder = new Array(m).fill(-1);     // applicant in each job
  const tryAssign = (a, tried) => {
    for (let j = 0; j < m; j++) {
      if (!matrix[a][j] || tried[j]) continue;
      tried[j] = true;
      if (holder[j] === -1 || tryAssign(holder[j], tried)) { holder[j] = a; return true; }
    }
    return false;
  };
  let placed = 0;
  for (let a = 0; a < n; a++) if (tryAssign(a, new Array(m).fill(false))) placed++;
  return placed;
}

fn solve<const M: usize>(matrix: &[[i64; M]]) -> i64 {
    fn try_assign<const M: usize>(a: usize, matrix: &[[i64; M]], holder: &mut Vec<Option<usize>>, tried: &mut Vec<bool>) -> bool {
        for j in 0..M {
            if matrix[a][j] == 0 || tried[j] {
                continue;
            }
            tried[j] = true;
            let free = match holder[j] {
                None => true,
                Some(h) => try_assign(h, matrix, holder, tried),
            };
            if free {
                holder[j] = Some(a);                  // a takes job j
                return true;
            }
        }
        false
    }
    let mut holder = vec![None; M];
    let mut placed = 0;
    for a in 0..matrix.len() {
        let mut tried = vec![false; M];               // a fresh search per applicant
        if try_assign(a, matrix, &mut holder, &mut tried) {
            placed += 1;
        }
    }
    placed
}

import qualified Data.Map.Strict as M
import qualified Data.Set as S

solve :: [[Int]] -> Int
solve matrix = fst (foldl place (0, M.empty) [0 .. length matrix - 1])
  where
    wants a = [j | (j, 1) <- zip [0 ..] (matrix !! a)]
    -- the state is (number placed, map from job to its applicant)
    place (k, holder) a = case tryAssign a S.empty holder of
      Right holder' -> (k + 1, holder')
      Left _ -> (k, holder)
    -- Right: the holders after an augmenting path; Left: the jobs tried, shared across the search
    tryAssign a tried holder = go (wants a) tried
      where
        go [] tr = Left tr
        go (j : js) tr
          | S.member j tr = go js tr
          | otherwise = case M.lookup j holder of
              Nothing -> Right (M.insert j a holder)
              Just h -> case tryAssign h (S.insert j tr) holder of
                Right holder' -> Right (M.insert j a holder')
                Left tr' -> go js tr'

The same code is the reference solution to Place as many applicants as possible, where it is compiled and run against the tests in all six languages.

TimeO(V · E)

SpaceO(V + E)

Each applicant runs at most one search over the edges. Hopcroft–Karp finds many shortest augmenting paths per round and runs in O(E √V), worth it only for very large graphs.

König's theorem: in a bipartite graph the size of a maximum matching equals the size of a minimum vertex cover. Interviewers occasionally ask for the cover; it can be read off the final search.