40.02Intermediate / Advanced4 topics20 min2 interactive animations

Bipartite matching

In a bipartite graph an augmenting path can be found with a simple DFS or BFS. Kuhn's algorithm repeats the DFS once per left vertex; Hopcroft-Karp finds many shortest augmenting paths per phase and is much faster on large graphs.

Learning goals

Run Kuhn's DFS augmenting-path algorithm by hand
Explain the BFS layers and the blocking DFS of Hopcroft-Karp
State matching-size bounds and Hall's condition
Relate vertex covers to matchings

Prerequisites

Matching basics (Lesson 40.01)DFS and BFS

Assigning n workers to n jobs by trying every pairing is hopeless, but each assignment problem has a hidden structure: moving one worker to another job may free a job for someone else. A DFS that follows those chains of moves solves it in polynomial time.

40.02.1

DFS augmenting paths

**Kuhn's algorithm** processes the left vertices one by one. For vertex u it runs a DFS that tries to find an augmenting path starting at u. The DFS looks at each neighbour v of u on the right: if v is free the path ends there; if v is matched to w, the DFS asks recursively whether w can switch to some other right vertex. When the recursion succeeds, every vertex on the path takes its new mate.

A seen array marks right vertices already tried **during this search**. Without it, the same dead end would be explored again and again. With it, each search touches every edge at most once, so one search costs O(E) and the whole algorithm O(V · E).

One processing pass over the left vertices is enough: if there is no augmenting path from u at the moment u is processed, there will be none later either, so a failed vertex never needs a second try. Open the animation with “Kuhn on a chain (long re-routing)”. The search from left vertex 2 finds 1′ taken, asks its mate 0 to move, which finds 0′ taken and asks its mate 1 to move, and only then reaches the free right vertex 2′. This chain of re-routing is what makes the method more than greedy.

Java

1static boolean tryAugment(int u, List<Integer>[] adj, boolean[] seen, int[] matchR) {
2    for (int v : adj[u]) {
3        if (seen[v]) continue;                                        // visit every right vertex at most once per search
4        seen[v] = true;
5        if (matchR[v] == -1 || tryAugment(matchR[v], adj, seen, matchR)) {   // v is free, or its mate can move elsewhere
6            matchR[v] = u;
7            return true;
8        }
9    }
10    return false;
11}
12static int kuhn(int left, int right, List<Integer>[] adj) {
13    int[] matchR = new int[right];
14    Arrays.fill(matchR, -1);
15    int size = 0;
16    for (int u = 0; u < left; u++) if (tryAugment(u, adj, new boolean[right], matchR)) size++;
17    return size;
18}

Worst

O(V · E)

Space

O(V + E)

Maximum bipartite matching: Kuhn's DFS and Hopcroft-Karp

Interactive · edit the input

left vertices 0, 1, … and right vertices 0′, 1′, …; green edges are matched · 10 vertices · 9 edges

free

0′

free

1′

free

2′

free

3′

free

4′

free

Search path being triedMatched edge or vertexRoot of the search

mate of each left vertex

free0

free1

free2

free3

free4

mate of each right vertex

free0′

free1′

free2′

free3′

free4′

Setup

Kuhn's algorithm: for each left vertex u in turn, run a DFS that looks for an augmenting path starting at u. Each search visits every right vertex at most once.

Step 1 / 27

Java

1static boolean tryAugment(int u, List<Integer>[] adj, boolean[] seen, int[] matchR) {
2    for (int v : adj[u]) {
3        if (seen[v]) continue;                                        // visit every right vertex at most once per search
4        seen[v] = true;
5        if (matchR[v] == -1 || tryAugment(matchR[v], adj, seen, matchR)) {   // v is free, or its mate can move elsewhere
6            matchR[v] = u;
7            return true;
8        }
9    }
10    return false;
11}
12static int kuhn(int left, int right, List<Integer>[] adj) {
13    int[] matchR = new int[right];
14    Arrays.fill(matchR, -1);
15    int size = 0;
16    for (int u = 0; u < left; u++) if (tryAugment(u, adj, new boolean[right], matchR)) size++;
17    return size;
18}
19static boolean layers(int left, List<Integer>[] adj, int[] matchL, int[] matchR, int[] dist) {
20    Deque<Integer> queue = new ArrayDeque<>();
21    for (int u = 0; u < left; u++) {
22        dist[u] = matchL[u] == -1 ? 0 : -1;                           // free left vertices form layer 0
23        if (dist[u] == 0) queue.add(u);
24    }
25    boolean found = false;
26    while (!queue.isEmpty()) {
27        int u = queue.poll();
28        for (int v : adj[u]) {
29            int w = matchR[v];
30            if (w == -1) found = true;                                // a free right vertex ends an augmenting path
31            else if (dist[w] == -1) { dist[w] = dist[u] + 1; queue.add(w); }
32        }
33    }
34    return found;
35}
36static boolean extend(int u, List<Integer>[] adj, int[] matchL, int[] matchR, int[] dist) {
37    for (int v : adj[u]) {
38        int w = matchR[v];
39        if (w == -1 || (dist[w] == dist[u] + 1 && extend(w, adj, matchL, matchR, dist))) {
40            matchL[u] = v;
41            matchR[v] = u;
42            return true;
43        }
44    }
45    dist[u] = -1;                                                     // dead end: skip u for the rest of the phase
46    return false;
47}
48static int hopcroftKarp(int left, int right, List<Integer>[] adj) {
49    int[] matchL = new int[left], matchR = new int[right], dist = new int[left];
50    Arrays.fill(matchL, -1);
51    Arrays.fill(matchR, -1);
52    int size = 0;
53    while (layers(left, adj, matchL, matchR, dist)) {                 // one phase: BFS layers, then vertex-disjoint DFS
54        for (int u = 0; u < left; u++) if (matchL[u] == -1 && extend(u, adj, matchL, matchR, dist)) size++;
55    }
56    return size;
57}

Live state

0 searches0 augmentations

left

right

edges

No condition evaluated on this step

Execution trace (dry run table)Show 27 steps

Step	Line	State	What happens
1	L12	left=5 right=5 edges=9	Kuhn's algorithm: for each left vertex u in turn, run a DFS that looks for an augmenting path starting at u. Each search visits every right vertex at most once.
2	L16	u=0 size=0	Search for an augmenting path from left vertex 0.
3	L5	u=0 v=0′ matchR[v]=free	0′ is free: the DFS has reached the end of an augmenting path.
4	L16	u=0 size=1	Success: the path is flipped and the matching grows to 1.
5	L16	u=1 size=1	Search for an augmenting path from left vertex 1.
6	L5	u=1 v=0′ matchR[v]=0	0′ is matched to 0. Ask 0 to move to another right vertex (recursive call).
7	L5	u=0 v=1′ matchR[v]=free	1′ is free: the DFS has reached the end of an augmenting path.
8	L16	u=1 size=2	Success: the path is flipped and the matching grows to 2.
9	L16	u=2 size=2	Search for an augmenting path from left vertex 2.
10	L5	u=2 v=1′ matchR[v]=0	1′ is matched to 0. Ask 0 to move to another right vertex (recursive call).
11	L5	u=0 v=0′ matchR[v]=1	0′ is matched to 1. Ask 1 to move to another right vertex (recursive call).
12	L5	u=1 v=2′ matchR[v]=free	2′ is free: the DFS has reached the end of an augmenting path.
13	L16	u=2 size=3	Success: the path is flipped and the matching grows to 3.
14	L16	u=3 size=3	Search for an augmenting path from left vertex 3.
15	L5	u=3 v=2′ matchR[v]=1	2′ is matched to 1. Ask 1 to move to another right vertex (recursive call).
16	L5	u=1 v=0′ matchR[v]=0	0′ is matched to 0. Ask 0 to move to another right vertex (recursive call).
17	L5	u=0 v=1′ matchR[v]=2	1′ is matched to 2. Ask 2 to move to another right vertex (recursive call).
18	L5	u=2 v=3′ matchR[v]=free	3′ is free: the DFS has reached the end of an augmenting path.
19	L16	u=3 size=4	Success: the path is flipped and the matching grows to 4.
20	L16	u=4 size=4	Search for an augmenting path from left vertex 4.
21	L5	u=4 v=3′ matchR[v]=2	3′ is matched to 2. Ask 2 to move to another right vertex (recursive call).
22	L5	u=2 v=1′ matchR[v]=0	1′ is matched to 0. Ask 0 to move to another right vertex (recursive call).
23	L5	u=0 v=0′ matchR[v]=1	0′ is matched to 1. Ask 1 to move to another right vertex (recursive call).
24	L5	u=1 v=2′ matchR[v]=3	2′ is matched to 3. Ask 3 to move to another right vertex (recursive call).
25	L5	u=3 v=4′ matchR[v]=free	4′ is free: the DFS has reached the end of an augmenting path.
26	L16	u=4 size=5	Success: the path is flipped and the matching grows to 5.
27	L17	return=5 augmentations=5	Maximum matching size 5, found with 5 augmentations.

40.02.2

Hopcroft-Karp

**Hopcroft-Karp** speeds this up by finding several augmenting paths in one go. A phase has two steps. First a BFS from **all** free left vertices at once assigns each left vertex a layer (layer 0 holds the free left vertices; layer 1 holds the left vertices reached through one non-matching edge and then a matching edge; and so on) and checks that some free right vertex is reachable. Then a DFS from each free left vertex follows only edges that go from layer d to layer d + 1, flipping every augmenting path it finds. Left vertices that turn out to be dead ends get dist = -1 so they are skipped for the rest of the phase.

The key fact is that after a phase the shortest augmenting path is strictly longer than before. A path of length ℓ implies at most about V / ℓ more augmentations, so the number of phases is O(√V); each phase is O(E). The total is O(E · √V), compared with O(V · E) for Kuhn.

Try the preset “Hopcroft-Karp on the same chain”. All five edges are placed in a single phase, while Kuhn needed five separate searches. With “Hopcroft-Karp, two phases” left vertex 1 finds its only neighbour 0′ already taken during the first phase, so the longer path that repairs it can only appear after the second BFS. On small inputs both algorithms are instant; the difference shows up at thousands of vertices.

	Kuhn (DFS)	Hopcroft-Karp
Idea	one augmenting path per left vertex	many vertex-disjoint paths per BFS phase
Time	O(V · E)	O(E · √V)
Code size	about 15 lines	about 40 lines
Use when	V up to a few thousand, or simplicity matters	large graphs, tight limits

Java

1static boolean layers(int left, List<Integer>[] adj, int[] matchL, int[] matchR, int[] dist) {
2    Deque<Integer> queue = new ArrayDeque<>();
3    for (int u = 0; u < left; u++) {
4        dist[u] = matchL[u] == -1 ? 0 : -1;                           // free left vertices form layer 0
5        if (dist[u] == 0) queue.add(u);
6    }
7    boolean found = false;
8    while (!queue.isEmpty()) {
9        int u = queue.poll();
10        for (int v : adj[u]) {
11            int w = matchR[v];
12            if (w == -1) found = true;                                // a free right vertex ends an augmenting path
13            else if (dist[w] == -1) { dist[w] = dist[u] + 1; queue.add(w); }
14        }
15    }
16    return found;
17}
18static boolean extend(int u, List<Integer>[] adj, int[] matchL, int[] matchR, int[] dist) {
19    for (int v : adj[u]) {
20        int w = matchR[v];
21        if (w == -1 || (dist[w] == dist[u] + 1 && extend(w, adj, matchL, matchR, dist))) {
22            matchL[u] = v;
23            matchR[v] = u;
24            return true;
25        }
26    }
27    dist[u] = -1;                                                     // dead end: skip u for the rest of the phase
28    return false;
29}
30static int hopcroftKarp(int left, int right, List<Integer>[] adj) {
31    int[] matchL = new int[left], matchR = new int[right], dist = new int[left];
32    Arrays.fill(matchL, -1);
33    Arrays.fill(matchR, -1);
34    int size = 0;
35    while (layers(left, adj, matchL, matchR, dist)) {                 // one phase: BFS layers, then vertex-disjoint DFS
36        for (int u = 0; u < left; u++) if (matchL[u] == -1 && extend(u, adj, matchL, matchR, dist)) size++;
37    }
38    return size;
39}

Worst

O(E · √V)

Space

O(V + E)

Maximum bipartite matching: Kuhn's DFS and Hopcroft-Karp

Interactive · edit the input

left vertices 0, 1, … and right vertices 0′, 1′, …; green edges are matched · 10 vertices · 9 edges

free

0′

free

1′

free

2′

free

3′

free

4′

free

Search path being triedMatched edge or vertexRoot of the search

mate of each left vertex

free0

free1

free2

free3

free4

mate of each right vertex

free0′

free1′

free2′

free3′

free4′

Setup

Kuhn's algorithm: for each left vertex u in turn, run a DFS that looks for an augmenting path starting at u. Each search visits every right vertex at most once.

Step 1 / 27

Java

1static boolean tryAugment(int u, List<Integer>[] adj, boolean[] seen, int[] matchR) {
2    for (int v : adj[u]) {
3        if (seen[v]) continue;                                        // visit every right vertex at most once per search
4        seen[v] = true;
5        if (matchR[v] == -1 || tryAugment(matchR[v], adj, seen, matchR)) {   // v is free, or its mate can move elsewhere
6            matchR[v] = u;
7            return true;
8        }
9    }
10    return false;
11}
12static int kuhn(int left, int right, List<Integer>[] adj) {
13    int[] matchR = new int[right];
14    Arrays.fill(matchR, -1);
15    int size = 0;
16    for (int u = 0; u < left; u++) if (tryAugment(u, adj, new boolean[right], matchR)) size++;
17    return size;
18}
19static boolean layers(int left, List<Integer>[] adj, int[] matchL, int[] matchR, int[] dist) {
20    Deque<Integer> queue = new ArrayDeque<>();
21    for (int u = 0; u < left; u++) {
22        dist[u] = matchL[u] == -1 ? 0 : -1;                           // free left vertices form layer 0
23        if (dist[u] == 0) queue.add(u);
24    }
25    boolean found = false;
26    while (!queue.isEmpty()) {
27        int u = queue.poll();
28        for (int v : adj[u]) {
29            int w = matchR[v];
30            if (w == -1) found = true;                                // a free right vertex ends an augmenting path
31            else if (dist[w] == -1) { dist[w] = dist[u] + 1; queue.add(w); }
32        }
33    }
34    return found;
35}
36static boolean extend(int u, List<Integer>[] adj, int[] matchL, int[] matchR, int[] dist) {
37    for (int v : adj[u]) {
38        int w = matchR[v];
39        if (w == -1 || (dist[w] == dist[u] + 1 && extend(w, adj, matchL, matchR, dist))) {
40            matchL[u] = v;
41            matchR[v] = u;
42            return true;
43        }
44    }
45    dist[u] = -1;                                                     // dead end: skip u for the rest of the phase
46    return false;
47}
48static int hopcroftKarp(int left, int right, List<Integer>[] adj) {
49    int[] matchL = new int[left], matchR = new int[right], dist = new int[left];
50    Arrays.fill(matchL, -1);
51    Arrays.fill(matchR, -1);
52    int size = 0;
53    while (layers(left, adj, matchL, matchR, dist)) {                 // one phase: BFS layers, then vertex-disjoint DFS
54        for (int u = 0; u < left; u++) if (matchL[u] == -1 && extend(u, adj, matchL, matchR, dist)) size++;
55    }
56    return size;
57}

Live state

0 searches0 augmentations

left

right

edges

No condition evaluated on this step

Execution trace (dry run table)Show 27 steps

Step	Line	State	What happens
1	L12	left=5 right=5 edges=9	Kuhn's algorithm: for each left vertex u in turn, run a DFS that looks for an augmenting path starting at u. Each search visits every right vertex at most once.
2	L16	u=0 size=0	Search for an augmenting path from left vertex 0.
3	L5	u=0 v=0′ matchR[v]=free	0′ is free: the DFS has reached the end of an augmenting path.
4	L16	u=0 size=1	Success: the path is flipped and the matching grows to 1.
5	L16	u=1 size=1	Search for an augmenting path from left vertex 1.
6	L5	u=1 v=0′ matchR[v]=0	0′ is matched to 0. Ask 0 to move to another right vertex (recursive call).
7	L5	u=0 v=1′ matchR[v]=free	1′ is free: the DFS has reached the end of an augmenting path.
8	L16	u=1 size=2	Success: the path is flipped and the matching grows to 2.
9	L16	u=2 size=2	Search for an augmenting path from left vertex 2.
10	L5	u=2 v=1′ matchR[v]=0	1′ is matched to 0. Ask 0 to move to another right vertex (recursive call).
11	L5	u=0 v=0′ matchR[v]=1	0′ is matched to 1. Ask 1 to move to another right vertex (recursive call).
12	L5	u=1 v=2′ matchR[v]=free	2′ is free: the DFS has reached the end of an augmenting path.
13	L16	u=2 size=3	Success: the path is flipped and the matching grows to 3.
14	L16	u=3 size=3	Search for an augmenting path from left vertex 3.
15	L5	u=3 v=2′ matchR[v]=1	2′ is matched to 1. Ask 1 to move to another right vertex (recursive call).
16	L5	u=1 v=0′ matchR[v]=0	0′ is matched to 0. Ask 0 to move to another right vertex (recursive call).
17	L5	u=0 v=1′ matchR[v]=2	1′ is matched to 2. Ask 2 to move to another right vertex (recursive call).
18	L5	u=2 v=3′ matchR[v]=free	3′ is free: the DFS has reached the end of an augmenting path.
19	L16	u=3 size=4	Success: the path is flipped and the matching grows to 4.
20	L16	u=4 size=4	Search for an augmenting path from left vertex 4.
21	L5	u=4 v=3′ matchR[v]=2	3′ is matched to 2. Ask 2 to move to another right vertex (recursive call).
22	L5	u=2 v=1′ matchR[v]=0	1′ is matched to 0. Ask 0 to move to another right vertex (recursive call).
23	L5	u=0 v=0′ matchR[v]=1	0′ is matched to 1. Ask 1 to move to another right vertex (recursive call).
24	L5	u=1 v=2′ matchR[v]=3	2′ is matched to 3. Ask 3 to move to another right vertex (recursive call).
25	L5	u=3 v=4′ matchR[v]=free	4′ is free: the DFS has reached the end of an augmenting path.
26	L16	u=4 size=5	Success: the path is flipped and the matching grows to 5.
27	L17	return=5 augmentations=5	Maximum matching size 5, found with 5 augmentations.

40.02.3

Matching size

The size of a maximum matching in a bipartite graph with L left and R right vertices is at most min(L, R), and at most the number of edges. A matching that uses every left vertex is called **left-perfect** or saturating; when L = R and every vertex is matched it is **perfect**.

**Hall's marriage theorem** says exactly when a left-saturating matching exists: for every set S of left vertices, the set N(S) of right vertices adjacent to some vertex of S must satisfy |N(S)| ≥ |S|. A set that violates this is a bottleneck, such as two workers who can only do the same single job. The code below finds a violating set by trying every subset, which is only for tiny inputs and for understanding; the algorithms above answer the same question in polynomial time.

In the animation, the preset “Workers and jobs (no perfect matching)” has left vertices 1 and 3 whose only neighbour is right vertex 0′. That set {1, 3} has |N| = 1 < 2, so no matching can use both, and the maximum matching has size 3 instead of 4.

Quantity	Bound or fact
Matching size	≤ min(L, R) and ≤ E
Left-saturating matching exists	iff \|N(S)\| ≥ \|S\| for every set S of left vertices (Hall)
Perfect matching in a bipartite graph	needs L = R and Hall's condition on both sides
Maximum matching size	equals the number of left vertices minus the largest deficiency \|S\| − \|N(S)\|

Java

1// nbr[u] = bit mask of the right vertices adjacent to left vertex u.
2// Returns a set S of left vertices with |N(S)| < |S| (as a bit mask), or 0 when Hall's condition holds.
3static int hallViolator(int[] nbr) {
4    int left = nbr.length;
5    for (int s = 1; s < (1 << left); s++) {
6        int neighbours = 0;
7        for (int u = 0; u < left; u++) if ((s >> u & 1) == 1) neighbours |= nbr[u];
8        if (Integer.bitCount(neighbours) < Integer.bitCount(s)) return s;
9    }
10    return 0;
11}

40.02.4

Vertex covers

A **vertex cover** is a set of vertices that touches every edge. Choosing vertices to cover edges is the opposite viewpoint to choosing edges that avoid each other, and the two are tightly linked.

Every cover is at least as large as every matching. The edges of a matching are pairwise vertex-disjoint, so covering them needs one distinct cover vertex per matching edge. This **weak duality** means a cover of size k and a matching of size k certify each other: the matching cannot be larger than k, and the cover cannot be smaller. The code below checks exactly that certificate.

In general graphs the minimum vertex cover problem is NP-hard, and a maximum matching only brackets it: |M| ≤ minimum cover ≤ 2|M|, because the matched vertices of a maximal matching form a cover. In **bipartite** graphs the bracket closes: the two numbers are equal. That is König's theorem, the subject of the next lesson. Closely related: the vertices outside a vertex cover form a maximum **independent set**, so in a bipartite graph α = V − ν (independence number equals vertices minus maximum matching size).

Object	Definition	Relation in a bipartite graph
Matching M	edges, no shared vertex	ν = max \|M\|
Vertex cover C	vertices touching every edge	τ = min \|C\| equals ν (König)
Independent set I	vertices, no edge between them	α = V − τ = V − ν
Edge cover	edges touching every vertex	ρ = V − ν when no vertex is isolated

Java

1static boolean isVertexCover(int[][] edges, boolean[] inCover) {      // every edge has a covered end
2    for (int[] e : edges) if (!inCover[e[0]] && !inCover[e[1]]) return false;
3    return true;
4}
5// a cover and a matching of the same size prove that both are optimal
6static boolean certifiesOptimal(int[][] edges, boolean[] inCover, int[][] matching) {
7    int size = 0;
8    for (boolean b : inCover) if (b) size++;
9    boolean[] used = new boolean[inCover.length];
10    for (int[] e : matching) {
11        if (used[e[0]] || used[e[1]]) return false;                   // not a matching
12        used[e[0]] = true;
13        used[e[1]] = true;
14    }
15    return isVertexCover(edges, inCover) && size == matching.length;
16}

Practice ladder

Now try it yourself

Easy

Is Graph Bipartite?

Medium

Maximum Number of Accepted Invitations

Advanced

Maximum Students Taking Exam

Key takeaways

Kuhn: one DFS per left vertex, O(V·E); the seen array keeps each search linear.
Hopcroft-Karp: BFS layers plus a blocking DFS per phase, O(E·√V).
A matching and a vertex cover of equal size certify each other; Hall's condition explains when a left-saturating matching exists.