← Lessons

quiz vs the machine

Gold1380

Algorithms

Bipartite Matching

Pairing items from two groups so each is used at most once.

5 min read · core · beat Gold to climb

Two sides and the pairing goal

A bipartite graph splits nodes into two groups with edges only between the groups, never inside one. Think of workers on the left, jobs on the right, and an edge wherever a worker can do a job. A matching is a set of edges where no node is used twice. The maximum matching pairs up as many as possible.

Augmenting paths again

A path that alternates between unmatched and matched edges, starting and ending at unmatched nodes, is an augmenting path. Flipping which edges along it are matched increases the matching size by exactly one. Keep finding augmenting paths until none remains; the result is a maximum matching.

Reduction to flow

You can also solve it as a flow problem. Add a source linked to every left node and a sink linked from every right node, give each edge capacity one, and the maximum flow equals the maximum matching. Each unit of flow is one chosen pair.

Konig insight

In bipartite graphs the size of a maximum matching equals the size of a minimum vertex cover, a small set of nodes touching every edge. This pleasing duality mirrors max flow min cut.

Key idea

Maximum bipartite matching pairs two groups using augmenting paths, and it reduces cleanly to a unit capacity max flow problem.

Check yourself

Answer to earn rating on the learn ladder.

1. What defines a matching in a bipartite graph?

2. How does flow capacity one help solve bipartite matching?