Bipartite matching

When every edge joins two kinds of thing, people and jobs, students and seats, pairing them up is a matching problem. Two colors tell you the graph has two sides, and augmenting paths pair up as many as possible.

3 examples6 to practiceRead · 5 min
The idea

Two sides, and every edge crosses between them

A bipartite graph is one whose nodes split into two sides so that every edge joins the two sides: no edge stays within one. People and the jobs they can do, students and the courses they want, rows and columns of a board. The pairing questions on such graphs have fast, exact answers.

A graph is bipartite exactly when it has no odd cycle, a cycle with an odd number of edges. Going around any cycle switches sides at every edge, so to return to the start the cycle needs an even number of edges. A triangle can never be split.

The rule

Check two sides by coloring: give the first node a color, every neighbor the other color, and fail when an edge joins two nodes of the same color. Pair the sides by augmenting paths: a new pair may move existing pairs along, as long as everyone stays matched.

Basic

Two colors decide whether there are two sides

Run a breadth-first search from any uncolored node. Give it side 0; each neighbor gets the opposite side of the node that reached it. If an edge ever joins two nodes already on the same side, that edge closes an odd cycle and the graph is not bipartite. Repeat from every node still uncolored, since the graph may come in several pieces.

Every node is colored once and every edge checked twice, once from each end: O(V + E), for V nodes and E edges (n and m on the graph pages). The coloring itself is the split into two sides when the check passes.

Medium

Matching by augmenting paths: let earlier pairs move over

A matching is a set of edges with no node used twice: each person gets at most one job and each job at most one person. A maximum matching has as many pairs as possible.

Take the people one at a time. For each, try the jobs they like. A free job is taken at once. A taken job can still be had if its current holder can move to another job they like, which may in turn ask its holder to move, and so on. Such a chain, alternating between an unused edge and a matched one and ending at a free job, is an alternating path; switching every edge along it adds one pair and keeps everyone matched. A seen set stops the chain from asking about the same job twice in one search.

Each person runs one search of O(E): O(V × E) in all. The Hopcroft-Karp algorithm finds many shortest alternating paths at once and needs O(E × √V).

Hard

Matching is a maximum flow with capacity 1

Add a source s with an edge to every person, an edge from every job to a sink t, and keep the person-to-job edges; give every edge capacity 1. A unit of flow is one pair: capacity 1 out of s lets a person take one job, capacity 1 into t lets a job take one person. So the maximum flow is the size of a maximum matching, and an augmenting path in this network is exactly an alternating path.

The reverse edge x→a in the last path is the move "a gives up x and takes y", the same move the search made in the previous example. Flow also handles variations a pure matching can't: a job with room for two people is an edge to t with capacity 2.

One more consequence. In a bipartite graph, the fewest nodes that touch every edge, a minimum vertex cover, equals the size of a maximum matching. It comes from the minimum cut of this network, and it is how problems that ask for the most nodes with no edge between them get solved.

LeetCode has few problems that need a flow algorithm: most problems that look like one are solved by matching, a plain search or bitmask dynamic programming, so the practice list below is short.

Check yourself

3 questions

1. A graph has a cycle of 5 edges. Can it be bipartite?
2. Person b likes only job x, which a already holds. a also likes y, which is free. What happens when b is matched?
3. In the flow network for a matching, why does every edge from s have capacity 1?
Takeaways

Remember this

  • A graph is bipartite exactly when it has no odd cycle; two-coloring by breadth-first search checks it in O(V + E).
  • A maximum matching grows one alternating path at a time: earlier pairs move over to make room.
  • Matching is maximum flow with capacity 1 everywhere; the residual graph's reverse edges are the moves.
  • Capacities above 1 extend matching to jobs with several places.
Practice

Now solve some yourself

Only this topic 0 of 1 solved

  1. Hard
    Most dance pairs from a list of willing pairs
    Bipartite matching
    CSES 1696(opens in a new tab)

Mixed with topics you have practiced 0 unlocked

    5 more once you have practiced BFS & DFS, Minimum cut. Play one of its examples to the end and solve one of its problems to unlock them.

    Problems open on their own sites (LeetCode, Codeforces, CodeChef, AtCoder, CSES) in a new tab. Tick Solved when you get it accepted there; your ticks decide which mixed problems open next.