12.9 Bipartite Matching

Problem

Suppose you have a set of workers and a set of tasks.

Each worker can perform only certain tasks.

Worker	Tasks
Alice	A, B
Bob	B, C
Carol	A, C

You want to assign as many workers as possible such that:

• Each worker receives at most one task.
• Each task is assigned to at most one worker.

This problem appears in many domains:

• Job assignment
• Course registration
• Mentor matching
• Advertisement allocation
• Resource scheduling
• Organ transplant matching
• Team formation

At first glance, matching seems unrelated to network flow. One problem deals with assignments while the other deals with moving quantities through edges.

The key insight is that matching can be modeled as a special flow network.

Solution

Represent the problem as a bipartite graph.

A bipartite graph contains two disjoint sets of vertices:

Left side
Right side

Edges connect only between the two sides.

For the worker-task example:

Workers          Tasks

Alice ---------> A
Alice ---------> B

Bob -----------> B
Bob -----------> C

Carol ---------> A
Carol ---------> C

A matching is a set of edges such that no vertex participates in more than one selected edge.

Definitions

Let:

L = left vertices
R = right vertices

A matching is a subset of edges:

M ⊆ E

such that every vertex appears in at most one edge of M.

Example:

Alice -> B
Bob   -> C
Carol -> A

This matching contains three assignments.

No worker appears twice.

No task appears twice.

Maximum Matching

The objective is usually:

Find the largest matching.

This is called the maximum bipartite matching problem.

Example:

Workers = 5
Tasks   = 4

The largest possible matching cannot exceed:

4

because only four tasks exist.

The goal is to find the best feasible assignment.

Transforming to a Flow Network

Construct a new graph.

Step 1: Add a Source

Create:

s

Connect source to every worker.

s -> Alice
s -> Bob
s -> Carol

Each edge receives capacity:

1

Step 2: Add Worker-Task Edges

For every valid assignment:

worker -> task

add an edge with capacity:

1

Step 3: Add a Sink

Create:

t

Connect every task to the sink.

A -> t
B -> t
C -> t

Each edge has capacity:

1

The resulting network:

          Alice
        ↗
s              ↘
                A
        ↘      ↗
          Bob
                 ↘
                   t
                 ↗
          Carol

All capacities equal one.

Why This Works

Consider the edge:

s -> Alice

with capacity:

1

At most one unit of flow can leave Alice.

Similarly:

A -> t

has capacity:

1

At most one unit of flow can enter task A.

As a result:

• Workers can be assigned at most once.
• Tasks can be assigned at most once.

Exactly the matching constraints we wanted.

Example

Workers:

Alice
Bob
Carol

Tasks:

A
B
C

Connections:

Alice -> A
Alice -> B

Bob -> B
Bob -> C

Carol -> A
Carol -> C

Maximum flow computation produces:

s -> Alice -> B -> t
s -> Bob   -> C -> t
s -> Carol -> A -> t

Flow value:

3

Matching:

Worker	Task
Alice	B
Bob	C
Carol	A

The matching size equals the flow value.

Why Unit Capacities Matter

All capacities are:

1

This guarantees every flow value is integral.

A worker either receives a task or does not.

Fractional assignments cannot occur.

Without unit capacities, strange solutions become possible.

Example:

Alice -> A = 0.5
Alice -> B = 0.5

which makes little sense for most assignment problems.

The integrality property prevents this.

Augmenting Paths in Matching

The residual graph has a natural interpretation.

Suppose the current matching contains:

Alice -> A

and:

Bob -> B

Now consider an unmatched worker:

Carol

and an unmatched task:

C

An augmenting path might be:

Carol -> A
A -> Alice
Alice -> B
B -> Bob
Bob -> C

Following this path:

• removes some assignments
• adds others
• increases matching size by one

This is exactly the same idea as augmenting paths in flow networks.

Hall's Marriage Theorem

One of the most important results in matching theory is Hall's theorem.

A perfect matching exists if and only if:

Every subset of workers is connected to at least as many tasks.

Example:

Workers:
Alice
Bob
Carol

Tasks:

A
B

Three workers cannot all be matched to only two tasks.

Hall's condition fails.

Flow formulations provide an algorithmic way to test such conditions.

Perfect Matching

A matching is perfect when every vertex on one side is matched.

Example:

Worker	Task
Alice	A
Bob	B
Carol	C

Every worker receives exactly one task.

Perfect matchings are common in:

• Scheduling
• Tournament design
• Resource allocation
• Assignment systems

Implementation Using Dinic

Because all capacities equal one, Dinic performs particularly well.

Complexity:

O(E√V)

for bipartite matching.

This is substantially faster than general maximum-flow bounds.

Many competitive programming solutions use Dinic directly for matching problems.

Extracting the Matching

After computing maximum flow:

Inspect all worker-task edges.

Any edge with flow:

1

belongs to the matching.

Example:

Edge	Flow
Alice -> B	1
Bob -> C	1
Carol -> A	1

These edges form the solution.

No additional work is required.

Common Modeling Patterns

Students and Courses

Student -> Course

if enrollment is allowed.

Employees and Shifts

Employee -> Shift

if availability exists.

Advertisements and Slots

Ad -> Slot

if placement is valid.

Mentors and Mentees

Mentor -> Student

if pairing is acceptable.

Each becomes a matching problem.

Common Mistakes

Forgetting Source Edges

Every left-side vertex needs:

source -> vertex

capacity one.

Forgetting Sink Edges

Every right-side vertex needs:

vertex -> sink

capacity one.

Using Large Capacities

Matching requires:

capacity = 1

for assignment constraints.

Misinterpreting Residual Edges

Reverse edges do not represent assignments.

They exist only for flow adjustment.

Complexity Analysis

Let:

• (V) = vertices
• (E) = edges

Using generic max flow:

Algorithm	Complexity
Edmonds-Karp	O(VE²)
Dinic	O(V²E)

For bipartite matching:

Algorithm	Complexity
Hopcroft-Karp	O(E√V)
Dinic (unit capacities)	O(E√V)

This special structure allows much faster algorithms.

Discussion

Bipartite matching is one of the most important examples of algorithmic modeling. The original problem does not mention flow, capacities, residual graphs, or cuts. Yet a simple transformation converts the entire problem into a maximum-flow instance.

This pattern appears repeatedly throughout optimization. Many difficult problems become straightforward once expressed as flow networks. The challenge is often not solving the network but recognizing that a network exists.

Takeaway

Maximum bipartite matching can be reduced directly to maximum flow by connecting the source to left-side vertices, the sink to right-side vertices, and assigning unit capacities throughout the network.

The resulting maximum-flow value equals the matching size, and the flow-carrying worker-task edges form the matching itself. This reduction serves as the foundation for many assignment, scheduling, allocation, and pairing algorithms. The next recipe builds on this idea and develops a specialized algorithm for bipartite matching: Hopcroft-Karp.