Skip to content
Tutorials Center
My learning

Topics

Lesson 22 of 36 · Coloring and Matching

Bipartite Matching and Augmenting Paths

Understand matchings, Berge's augmenting path theorem and build Kuhn's and Hopcroft-Karp algorithms in Python to pair workers with jobs, checked against SciPy.

You have five workers and five jobs. Each worker can do only some of the jobs. Can every job be filled, and if not, what is the largest number of jobs you can assign so that nobody does two jobs and no job gets two workers? This is a matching problem, and it appears everywhere: assigning students to projects, doctors to shifts, ads to slots, and tasks to machines.

In this lesson you will learn the vocabulary, the key idea of augmenting paths, and write two classic algorithms that find a maximum matching in a bipartite graph.

Matchings: the definitions

A matching in a graph is a set of edges, no two of which share a vertex. Terms you will meet:

  • Maximal matching: cannot be extended by adding another edge. Easy to get greedily.
  • Maximum matching: has the largest possible number of edges. A maximum matching is always maximal, but a maximal matching can be only half the size of a maximum one.
  • Perfect matching: covers every vertex. Needs an even number of vertices.
  • A vertex touched by a matching edge is matched; otherwise it is free (exposed).

In a bipartite graph the vertices split into two sides L and R (workers and jobs) and edges only go between the sides, as you saw in coloring basics. Bipartite matching is solvable in polynomial time. (General graphs need Edmonds' blossom algorithm; the principle is similar, with extra machinery.)

flowchart LR
    subgraph Workers
      w1((w1))
      w2((w2))
      w3((w3))
    end
    subgraph Jobs
      j1((j1))
      j2((j2))
      j3((j3))
    end
    w1 --- j1
    w1 --- j2
    w2 --- j1
    w3 --- j2
    w3 --- j3

A small worker/job graph. Choosing w1-j1 greedily blocks w2 (who can only do j1), yet a perfect matching exists.

Alternating and augmenting paths

Fix a matching M. An alternating path walks along edges that alternately are not in M and are in M. An augmenting path is an alternating path that starts at a free vertex and ends at a different free vertex. It has odd length: one more non-matching edge than matching edges.

Flip the edges along an augmenting path (matching edges leave, non-matching edges join) and the matching grows by exactly one edge. This leads to the central result:

Berge's theorem. A matching is maximum if and only if the graph has no augmenting path with respect to it.

So the algorithm writes itself: start with any matching, repeatedly find an augmenting path, and flip it. When no augmenting path exists, you are done.

Growing a matching

Find a free vertex Start on the left side
Alternate Non-matching, then matching edges
Reach a free vertex That is an augmenting path
Flip it Matching grows by one

Repeat until no augmenting path exists

1 / 2

Kuhn's algorithm

Kuhn's algorithm tries, for each left vertex, to find an augmenting path by depth-first search. The recursive function try_assign(u) examines each neighbor v of u: if v is free, or if the vertex currently matched to v can be re-assigned elsewhere (a recursive call), then u takes v. The visited set stops us looping within one search.

Python Kuhn's algorithm: workers and jobs

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.

Greedy gives ana design, so ben has nothing left. Kuhn's algorithm, when it processes ben, discovers that ana can move to test, which frees design. That reshuffling is exactly an augmenting path: ben - design - ana - test.

Complexity. Each of the |L| searches costs O(E), so Kuhn is O(V·E). It is short to code and fast enough for thousands of vertices, but for large instances you want something better.

Hopcroft-Karp: many augmenting paths at once

The Hopcroft-Karp algorithm works in phases. Each phase:

  1. Runs a BFS from all free left vertices to compute layers (distance in alternating edges).
  2. Runs DFS only along layered edges to find a maximal set of vertex-disjoint shortest augmenting paths.
  3. Flips all of them together.

The shortest augmenting path length strictly increases every phase, and it can be shown that only O(√V) phases are needed, for a total of O(E·√V).

Python Hopcroft-Karp compared with SciPy

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.

Both implementations agree on the size (the exact pairs can differ because many maximum matchings may exist). The phase count is tiny compared to the 300 vertices, which is the whole point of Hopcroft-Karp.

Where matching shows up

  • Assignment problems. Workers to tasks, students to supervisors. With weights, the problem becomes the assignment problem, solved by the Hungarian algorithm (scipy.optimize.linear_sum_assignment).
  • Covering. A minimum number of rooks to cover every marked cell of a chessboard, or lines to cover points in a grid, equals a maximum matching (see König's theorem).
  • Edge coloring. Each color class in a proper edge coloring is a matching.
  • Max flow. Matching is a special case of maximum flow; add a source and a sink and the augmenting paths are flow paths.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. What is an augmenting path with respect to a matching M?

    An augmenting path alternates between non-matching and matching edges and has free vertices at both ends, so flipping it grows the matching by one.
  2. 2. Berge's theorem says a matching is maximum exactly when

    If an augmenting path existed we could enlarge the matching; conversely, if the matching is not maximum an augmenting path must exist.
  3. 3. Why can a maximal matching be much smaller than a maximum matching?

    A greedy matching can block itself; augmenting paths reshuffle earlier choices. A maximal matching is at least half the size of a maximum one, but not necessarily equal.
  4. 4. What is the running time of Hopcroft-Karp on a bipartite graph with V vertices and E edges?

    It needs O(sqrt(V)) phases, and each phase (a BFS plus a DFS over layered edges) costs O(E).

Summary

  • A matching is a set of pairwise non-touching edges; maximum matchings have the most edges, perfect matchings cover every vertex.
  • Flipping an augmenting path enlarges a matching by one; Berge's theorem says no such path means the matching is maximum.
  • Kuhn's DFS algorithm is simple and runs in O(V·E).
  • Hopcroft-Karp finds many shortest augmenting paths per phase and runs in O(E·√V).
  • Greedy choices can fail where augmenting paths succeed.

Next: Hall's Theorem, König's Theorem and Stable Matching