Bipartite Matching Generator
Given who can cover which shifts, how many people can be placed at once? Greedy assignment gets stuck: a perfectly reasonable first choice can block two later ones. The augmenting-path method escapes that by rearranging earlier decisions, and the striking part is that the answer can be proved optimal without trying every arrangement — König's theorem says the largest matching and the smallest set of rows and columns covering every option are the same size, and this page builds both.
What this generator does
Builds a random availability table between people and slots, then finds a maximum matching with Kuhn's augmenting-path algorithm. It separately constructs a minimum vertex cover by alternating search from the unmatched people, and confirms the two are the same size — which is exactly König's theorem and exactly why the matching is known to be optimal.
How to use this tool
- Set how many people, how many slots, and how likely each person is free for each slot.
- Try to place everyone yourself before generating.
- Generate, and read how many could be placed at once.
- Compare the matching size against the minimum cover — they always agree, and that is the proof.
Understanding the controls
- How many people
- Between 2 and 8. Everyone is guaranteed at least one slot they could take, because an empty row makes a dull problem rather than a hard one.
- How many slots
- Between 2 and 8. Fewer slots than people guarantees somebody goes without.
- Availability (%)
- How likely each person can take each slot. Low values make the problem tight and the greedy trap obvious.
- Seed
- Any word reproduces the same availability table and the same answer.
Common use cases
- Teaching maximum matching with an optimality proof rather than an assertion
- Shift and volunteer allocation worked examples
- Showing why greedy assignment leaves people unplaced
- Test instances for an assignment implementation
- Setting the same availability problem twice from a seed
How this generator works
Kuhn's algorithm tries to place each person in turn; when every slot they could take is occupied it asks the current holder to move, recursively, and takes the slot only if that rearrangement succeeds. The cover is built independently: mark every unmatched person, follow their options to slots, and from each slot follow its current holder back. The cover is then the unmarked people plus the marked slots, and its size matching the number of pairs is the optimality certificate.
Randomness and fairness
The availability table is random; the matching and the cover are computed and cross-checked against each other. A seed reproduces the table exactly and is therefore explicitly not cryptographically secure. Without a seed the browser's cryptographically secure generator is used.
For how randomness is produced across the whole site, see how Generate Random works.
Limitations and good to know
- Every slot holds one person — capacities above one are a different problem.
- Availability is unweighted, so this maximises how many are placed, not how happy they are.
- Names are generic placeholders; the page is about the structure, not the people.
- Eight by eight is the ceiling, which keeps the table readable on a phone.
- A generated matching problem is gone on reload — the seed is what reproduces it.
Privacy and your data
The table and the matching are computed entirely in your browser. Nothing about the problem or your seed is transmitted or kept.
Related generators
- Topological Order GeneratorDependency graphs with a valid task order, every edge checked to point forwards and the number of alternative orders counted exactly.
- Random Team GeneratorSplit a list of names into a chosen number of random, evenly sized teams.
- Shift Coverage GeneratorWorks out which shifts to roster so every hour's demand is met, and shows the paid slack that fixed-length shifts make unavoidable.
- Graph Centrality CalculatorDegree, closeness and betweenness for every node of a random network, each recomputed from scratch by breadth-first search before it is shown.