Skip to content
Tutorials Center
My learning

Topics

Lesson 45 of 68 ยท Graph Theory

Matching Algorithms: Augmenting Paths, Hopcroft-Karp and the Hungarian Method

Find maximum matchings with augmenting paths (Kuhn's algorithm), speed them up with Hopcroft-Karp, solve cheapest assignments with the Hungarian method, and meet the blossom algorithm.

A matching is a set of edges that share no endpoints. The lesson on independent sets, covers and matching defined the objects; this lesson shows how to actually compute the best ones. Matching problems are everywhere: assigning jobs to workers, students to projects, riders to drivers, doctors to hospital slots, even tiling a chessboard with dominoes.

There are three versions of the question, each with its own algorithm:

  1. Maximum cardinality matching: as many pairs as possible (bipartite: augmenting paths, Hopcroft-Karp).
  2. Minimum-cost perfect matching in a bipartite graph: the assignment problem (Hungarian algorithm).
  3. Maximum matching in a general, non-bipartite graph: Edmonds' blossom algorithm.

Augmenting paths

Fix a matching M. A vertex is matched if an edge of M touches it and free otherwise. An alternating path alternates between edges that are not in M and edges that are. An augmenting path is an alternating path that starts and ends at free vertices.

An augmenting path has one more non-matching edge than matching edges. Swap the roles of the edges along it (matching edges leave, non-matching edges join) and the matching grows by exactly one.

Berge's theorem: a matching is maximum if and only if it has no augmenting path. So the recipe for a maximum matching is: start with any matching, find an augmenting path, flip it, and repeat until none exists.

flowchart LR
    A["free left vertex u"] -->|"non-matching edge"| B["right vertex v"]
    B -->|"matching edge"| C["left vertex w"]
    C -->|"non-matching edge"| D["free right vertex x"]

An augmenting path: free, non-matching, matching, non-matching, free. Flipping it adds one edge to the matching.

Kuhn's algorithm (bipartite)

For each left vertex u in turn, try to find an augmenting path starting at u with a depth-first search: for each neighbor v, either v is free (done), or v is matched to some w and we try to re-route w somewhere else. Each search costs O(E), so the total is O(V E), fast enough for graphs with thousands of vertices.

Two classical facts come with it:

  • Hall's theorem: a bipartite graph has a matching that covers every left vertex if and only if every set S of left vertices has at least |S| neighbors: |N(S)| >= |S|.
  • Konig's theorem: in a bipartite graph, the size of a maximum matching equals the size of a minimum vertex cover.
Python Kuhn's algorithm, Hall's condition and Konig's theorem

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Hopcroft-Karp: many augmenting paths at once

Kuhn's algorithm finds one augmenting path per search. Hopcroft-Karp finds a whole batch of shortest augmenting paths in each phase:

  1. BFS from all free left vertices simultaneously, layering the graph by distance.
  2. DFS along the layers to find a maximal set of vertex-disjoint shortest augmenting paths, and flip them all.
  3. Repeat until the BFS finds no augmenting path.

The shortest augmenting path length strictly grows each phase, and it can be shown that only O(sqrt(V)) phases are needed, giving a running time of O(E sqrt(V)). For big bipartite graphs (a million edges) this is the standard algorithm.

Python Hopcroft-Karp on a bigger graph

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The domino check reproduces a classic puzzle. Every domino covers one black and one white square, and removing two same-coloured corners leaves 16 of one colour and 18 of the other, so a full tiling is impossible; the matching algorithm finds that the best you can do is 16 dominoes.

The assignment problem and the Hungarian algorithm

Often the edges have costs: worker i doing job j takes cost[i][j] hours. A minimum-cost perfect matching in the complete bipartite graph is the assignment problem. Trying all n! assignments is hopeless for even 15 workers; the Hungarian algorithm (Kuhn and Munkres) solves it in O(n^3).

Its idea is to keep a potential u[i] for each worker and v[j] for each job such that u[i] + v[j] <= cost[i][j] for every pair. Edges where equality holds are "tight". If a perfect matching exists using only tight edges, it is optimal, because any assignment costs at least the sum of the potentials. Otherwise the algorithm adjusts the potentials by the smallest slack to create new tight edges and continues the augmenting-path search.

Python Hungarian algorithm against brute force

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

To maximize a total (a profit matrix) instead, subtract every entry from the largest entry and minimize, or negate the matrix.

General graphs: the blossom algorithm

When the graph is not bipartite, augmenting-path search can get stuck at an odd cycle: the search wanders around the cycle and cannot tell which way an alternating path should leave it. In 1965 Jack Edmonds solved this with the blossom algorithm: contract each odd cycle ("blossom") of the alternating search tree into a single super-vertex, continue the search in the smaller graph, and expand it afterwards. Berge's theorem still holds in general graphs, and the algorithm finds a maximum matching in polynomial time (O(V^3) in the simple version, O(V E) with better bookkeeping). Libraries such as NetworkX and Boost provide implementations, so in practice you call one rather than write it.

Applications

  • Job and task assignment, school or hospital matching: bipartite matching and Hall's condition.
  • Cost-optimal assignment of drivers to riders or tasks to machines: Hungarian algorithm.
  • Tiling problems (dominoes) and bipartite vertex covers (Konig).
  • Scheduling and resource allocation: model resources and demands as the two sides.
  • Ride-sharing, roommate pairing, tournament pairing: general matching with the blossom algorithm.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What is an augmenting path?

    It starts and ends at unmatched vertices and alternates between non-matching and matching edges; flipping it grows the matching by one.
  2. 2. Berge's theorem says a matching M is maximum if and only if:

    If an augmenting path exists the matching can grow, so M is not maximum; conversely, if M is not maximum an augmenting path exists.
  3. 3. What is the running time of the Hopcroft-Karp algorithm?

    Only O(sqrt(V)) phases are needed and each phase costs O(E).
  4. 4. Konig's theorem states that in a bipartite graph the maximum matching size equals:

    Maximum matching and minimum vertex cover are equal in size for bipartite graphs.
  5. 5. Which algorithm solves minimum-cost perfect matching in a bipartite graph in O(n^3)?

    The Hungarian (Kuhn-Munkres) algorithm solves the assignment problem by maintaining potentials on both sides.

Summary

  • A matching grows by flipping an augmenting path; Berge's theorem says it is maximum exactly when none exists.
  • Kuhn's DFS algorithm runs in O(V E); Hopcroft-Karp batches shortest augmenting paths for O(E sqrt(V)).
  • Hall's theorem tests for matchings that cover one side; Konig's theorem equates maximum matching and minimum vertex cover in bipartite graphs.
  • The Hungarian algorithm solves the min-cost assignment problem in O(n^3) using potentials.
  • Non-bipartite graphs need the blossom algorithm, which contracts odd cycles.

Next: Trees and Spanning Trees.