Network Flow8 min read

Bipartite Matching

Match students to internships — find the maximum number of happy pairs
Hopcroft-Karp:\(O(E√V)\)simple DFS:\(O(V·E)\)König's theorem:max matching = min vertex cover

100 students, 100 companies. Each student applied to a few companies, and each company can hire at most one student. What's the maximum number of students who get a job?

That's bipartite matching — one of the most practically useful graph problems in computer science, with applications from scheduling to ad auctions to DNA analysis.

What Makes a Graph Bipartite?

A graph is bipartite if you can split all vertices into two groups — call them Left (L) and Right (R) — where every edge goes between L and R. No edges within L, no edges within R. Students on the left, companies on the right, job applications as edges.

A matching is a subset of edges where no vertex appears twice — each student in at most one pair, each company in at most one pair. We want the maximum matching: as many pairs as possible.

Augmenting Paths: The Key Idea

Given a partial matching, an augmenting path is a path that alternates between unmatched and matched edges, starting and ending at unmatched vertices. If you flip all edges on this path (matched→unmatched, unmatched→matched), the matching gains one pair.

Berge's theorem: a matching is maximum if and only if no augmenting path exists. So the algorithm is: keep finding and augmenting along augmenting paths until none remain. Simple DFS/BFS to find each path gives \(O(VE)\).

Hopcroft-Karp: The Faster Way

Instead of finding one augmenting path at a time, Hopcroft-Karp finds all shortest augmenting paths simultaneously in each phase:

  1. BFS phase: find the length of all shortest augmenting paths and build a layered graph.
  2. DFS phase: find a maximal set of vertex-disjoint augmenting paths in the layered graph and augment all at once.

After each phase, the length of the shortest remaining augmenting path strictly increases. This happens at most \(O(√V)\) times, giving \(O(√V)\) phases × \(O(E)\) per phase = \(O(E√V)\).

Reduction to Max Flow

Bipartite matching is secretly a max flow problem. Add a super-source s connected to every L vertex (capacity 1), a super-sink t from every R vertex (capacity 1), and keep all L-R edges with capacity 1. Run any max flow algorithm — the result equals the maximum matching.

Running Dinic's on this unit-capacity network gives \(O(E√V)\) — the same as Hopcroft-Karp.

König's Theorem

A vertex cover is a set of vertices that "touches" every edge (every edge has at least one endpoint in the cover). In bipartite graphs:

maximum matching size = minimum vertex cover size

This elegant duality — König's theorem — does not hold for general graphs (where min vertex cover is NP-hard). A minimum vertex cover can be found from a maximum matching using an alternating-path construction.

Note: Augmenting paths sound complicated but the idea is simple: find a chain of alternating matched/unmatched edges from one free vertex to another free vertex, then flip all of them. One flip = one extra matched pair.

Bipartite Matching — DFS Augmenting Paths

def bipartite_matching(left_n, right_n, edges):
    """edges: list of (l, r) where l in [0,left_n), r in [0,right_n)"""
    adj = [[] for _ in range(left_n)]
    for l, r in edges:
        adj[l].append(r)


    match_l = [-1] * left_n   # match_l[l] = r matched to l
    match_r = [-1] * right_n  # match_r[r] = l matched to r


    def dfs(l, visited):
        for r in adj[l]:
            if visited[r]: continue
            visited[r] = True
            if match_r[r] == -1 or dfs(match_r[r], visited):
                match_l[l] = r
                match_r[r] = l
                return True
        return False


    total = 0
    for l in range(left_n):
        visited = [False] * right_n
        if dfs(l, visited):
            total += 1


    return total, match_l


# 3 students, 3 companies
# student 0 -> companies 0,1
# student 1 -> companies 1
# student 2 -> companies 1,2
edges = [(0,0),(0,1),(1,1),(2,1),(2,2)]
count, matching = bipartite_matching(3, 3, edges)
print('Matched:', count)      # 3
print('Assignment:', matching) # [0, 1, 2]
Output
Matched: 3
Assignment: [0, 1, 2]

Complexity

⚡ Hopcroft-Karp\(O(√V)\) phases (path length increases each phase) × \(O(E)\) per phase; optimal for dense bipartite graphs
Near-linear for sparse graphs\(O(E√V)\)
🔍 Simple DFS augmenting pathsAt most V/2 augmentations; each DFS costs \(O(E)\); simple to implement correctly
Adequate for small graphs\(O(V·E)\)
🌊 Via Dinic's max flowUnit-capacity flow network; Dinic's achieves Hopcroft-Karp's complexity automatically
Same bound as Hopcroft-Karp\(O(E√V)\)
👑 König's theorem derivationAlternating BFS from unmatched L vertices finds minimum vertex cover from max matching
Linear after matching found\(O(V+E)\)

Quick check

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

Continue reading

Max Flow / Min Cut
How much water fits through your pipe network? The bottleneck decides
→
Dinic's Algorithm
Batch all shortest augmenting paths in one go — dramatically faster than one at a time
→
Hungarian Algorithm
Assign workers to tasks at the lowest possible total cost — the perfect match
→