Algorithms / Flow Matching Lite
Least You Need to Know: Flow and Matching Lite for Assignment-Style Problems
Maximum flow and bipartite matching give a powerful modeling layer for assignment, routing, and disjointness problems. The main idea is to convert local compatibility and capacity limits into edges and capacities so that feasible collections of pairings correspond to integral flow.
The least you need to know
- Bipartite matching asks for as many disjoint compatible pairs as possible between two sides.
- A standard reduction sends source-to-left, left-to-right compatibility, and right-to-sink edges with capacity 1.
- Capacity expresses how much can pass through an edge or resource.
- Many assignment-style constraints become matching or flow after the right graph model.
- Flow and shortest path optimize different objectives.
Key notation
capacity
maximum amount of flow allowed on an edge
matching
set of disjoint compatible pairs
max flow
largest feasible amount sent from source to sink
Tiny worked example
- Suppose interns must be assigned to projects they are qualified for.
- Put interns on the left and projects on the right.
- Add an edge for each allowed assignment.
- Connect source to each intern and each project to sink with capacity 1.
- A maximum matching then finds the largest compatible assignment set.
Common mistakes
- Students often reach for shortest paths when the real issue is disjoint assignment.
- Capacity 1 is the key signal for one-to-one matching.
- The graph model matters: compatibility becomes adjacency, and quotas become capacities.
How to recognize this kind of problem
- The prompt is about pairing, assignment, throughput, or disjoint routes.
- Compatibility and capacity constraints are more central than path length.
- A bipartite structure or source-sink throughput interpretation appears naturally.