Introduction

You have applicants and jobs, and lines connecting each applicant to the jobs they're qualified for. You want to hire as many people as possible — pair each to a job they can do, with nobody double-booked. The same shape appears everywhere: students to projects, riders to drivers, donors to patients.

The tempting approach is greedy: walk through the connections and grab any pair that still fits. It's quick — but it can paint itself into a corner. An early, hasty pairing can block two other pairings that would have worked, leaving people unmatched who didn't have to be.

That's the maximum matching problem: find the largest set of pairs. And here's the cheerful news, fitting for a finale: it's easy. Unlike the NP-hard problems across this site, maximum matching is solvable exactly, in polynomial time — and it's the engine inside assignment and kidney exchange.

Make the Pairs

Try it. On the left are applicants, on the right are jobs, and the lines show who can do what. Click a line to pair them (each person can be in only one pair). Make as many pairs as you can.

<p class="hint">Applicants on the left, jobs on the right; lines show who can do what. Click a line to <span class="g">pair</span> them (each person in only one pair). Make as many pairs as you can — then compare greedy vs the true maximum.</p>
<svg id="svg" viewBox="0 0 300 220" class="svg"></svg>
<div class="meter">Pairs made: <b id="count" class="g">0</b><span id="status" class="status"></span></div>
<div class="btns">
  <button id="greedy" type="button">Greedy</button>
  <button id="max" type="button">Maximum</button>
  <button id="reset" type="button" class="ghost">Clear</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.hint .g { color: #0a7d33; font-weight: 700; }
.svg { width: 100%; max-width: 380px; background: #f4f7f9; border: 1px solid #e2e6eb; border-radius: 10px; display: block; }
.edge { stroke: #c2ccd6; stroke-width: 3; cursor: pointer; }
.edge:hover { stroke: #8aa0b3; }
.edge.on { stroke: #2a9d8f; stroke-width: 5; }
.node { fill: #457b9d; }
.node.matched { fill: #2a9d8f; }
.nlbl { fill: #fff; font: 800 13px ui-monospace, monospace; text-anchor: middle; dominant-baseline: central; pointer-events: none; }
.meter { margin: .8rem 0 .6rem; font-size: 1.05rem; }
.g { color: #0a7d33; font-family: ui-monospace, monospace; }
.status { margin-left: .6rem; font: 700 .9rem system-ui; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .5rem 1rem; border: 1px solid #457b9d; background: #457b9d; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #457b9d; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Maximum bipartite matching (polynomial). Greedy grabs pairs in order and can get stuck; the maximum uses augmenting paths (Kuhn's algorithm) to rearrange and fit one more. Here greedy=2, maximum=3.
const L = ['a', 'b', 'c'], R = ['x', 'y', 'z'];
const EDGES = [['a', 'x'], ['a', 'y'], ['b', 'y'], ['b', 'z'], ['c', 'z']];
const adj = {}; L.forEach(u => adj[u] = []); EDGES.forEach(([u, v]) => adj[u].push(v));
const LP = { a: [70, 50], b: [70, 110], c: [70, 170] };
const RP = { x: [230, 50], y: [230, 110], z: [230, 170] };
let matched = new Set(); // set of "u-v" strings

function nodeMatched(n) { for (const e of matched) { const [u, v] = e.split('-'); if (u === n || v === n) return true; } return false; }
function canAdd(u, v) { return !nodeMatched(u) && !nodeMatched(v); }

function render() {
  let s = '';
  EDGES.forEach(([u, v]) => { const on = matched.has(u + '-' + v); s += '<line class="edge' + (on ? ' on' : '') + '" x1="' + LP[u][0] + '" y1="' + LP[u][1] + '" x2="' + RP[v][0] + '" y2="' + RP[v][1] + '" data-u="' + u + '" data-v="' + v + '"/>'; });
  L.forEach(u => { const m = nodeMatched(u); s += '<circle class="node' + (m ? ' matched' : '') + '" cx="' + LP[u][0] + '" cy="' + LP[u][1] + '" r="16"/><text class="nlbl" x="' + LP[u][0] + '" y="' + LP[u][1] + '">' + u + '</text>'; });
  R.forEach(v => { const m = nodeMatched(v); s += '<circle class="node' + (m ? ' matched' : '') + '" cx="' + RP[v][0] + '" cy="' + RP[v][1] + '" r="16"/><text class="nlbl" x="' + RP[v][0] + '" y="' + RP[v][1] + '">' + v + '</text>'; });
  document.getElementById('svg').innerHTML = s;
  document.getElementById('svg').querySelectorAll('.edge').forEach(el => el.addEventListener('click', () => {
    const u = el.dataset.u, v = el.dataset.v, key = u + '-' + v;
    if (matched.has(key)) matched.delete(key);
    else if (canAdd(u, v)) matched.add(key);
    render();
  }));
  document.getElementById('count').textContent = matched.size;
  const st = document.getElementById('status');
  if (matched.size === MAX) { st.style.color = '#0a7d33'; st.textContent = fmt('✓ maximum matching! (%MAX% pairs)', { MAX: MAX }); }
  else { st.style.color = '#777'; st.textContent = fmt('maximum possible is %MAX%', { MAX: MAX }); }
}

// Kuhn's algorithm for the true maximum
function maximum() {
  const matchR = {};
  function aug(u, seen) { for (const v of adj[u]) { if (seen.has(v)) continue; seen.add(v); if (matchR[v] === undefined || aug(matchR[v], seen)) { matchR[v] = u; return true; } } return false; }
  L.forEach(u => aug(u, new Set()));
  matched = new Set(Object.entries(matchR).map(([v, u]) => u + '-' + v));
  render();
}
const MAX = (function () { const matchR = {}; function aug(u, seen) { for (const v of adj[u]) { if (seen.has(v)) continue; seen.add(v); if (matchR[v] === undefined || aug(matchR[v], seen)) { matchR[v] = u; return true; } } return false; } L.forEach(u => aug(u, new Set())); return Object.keys(matchR).length; })();

function greedy() {
  const order = [['a', 'y'], ['b', 'z'], ['c', 'z'], ['a', 'x'], ['b', 'y']];
  matched = new Set(); const uL = new Set(), uR = new Set();
  for (const [u, v] of order) if (!uL.has(u) && !uR.has(v)) { matched.add(u + '-' + v); uL.add(u); uR.add(v); }
  render();
}

document.getElementById('greedy').addEventListener('click', greedy);
document.getElementById('max').addEventListener('click', maximum);
document.getElementById('reset').addEventListener('click', () => { matched = new Set(); render(); });
render();
Result
Console

Then compare. Greedy grabs pairs in order and gets stuck at fewer than the best. Maximum uses augmenting paths — it can rearrange existing pairs to free everyone up — and finds the true largest matching. Watch greedy settle for less while the optimal method squeezes in one more pair.

The Good News

Maximum matching is one of the prettiest solved problems in all of algorithms:

  • Checking is easy. Confirm no node is in two pairs and count the pairs.
  • Greedy is not optimal. As the demo shows, a hasty greedy can miss pairs — so we need something smarter.
  • Augmenting paths are the key idea. An augmenting path alternates between unmatched and matched edges and starts and ends at free nodes. Flip its edges and you gain exactly one pair. Keep finding them until none remain, and you've reached the maximum — that's Berge's theorem.
  • It's polynomial. Hopcroft–Karp matches bipartite graphs in O(E⋅V)O(E \cdot \sqrt{V}). For general (non-bipartite) graphs, odd cycles cause trouble, but Edmonds' Blossom algorithm (1965) handles them — a landmark result and an early definition of "efficient."
  • Weighted, too. Add costs and you get minimum-cost matching — the assignment problem, solved by the Hungarian algorithm — and a special case of min-cost flow.

So matching sits squarely in the friendly, conquered part of the complexity map — exact, fast, and the foundation for several other problems on this site.

Where It Matters

Pairing things up optimally is everywhere people and resources meet:

  • Markets: matching job applicants to positions, students to schools, users to recommendations.
  • Ride-hailing and dispatch: pairing riders with the right drivers in real time.
  • Kidney exchange: at its heart, organ matching is a matching problem (with extra constraints).
  • Scheduling: assigning tasks to time slots or workers to shifts.
  • Computer vision: matching features between images is a matching problem.

Because it's exact and fast, maximum matching is a quiet building block inside countless systems — often as the polynomial core that bigger, harder problems are built on.

Conclusion

Maximum matching is a fitting place to end. After cliffs of NP-hardness and ceilings of undecidability, here's a problem that's deep, useful, and solved — beautifully. The trick isn't brute force; it's the augmenting path, the elegant idea that you can always do better by rearranging what you have until no improvement remains.

It also ties the whole collection together: matching is the polynomial heart beating inside assignment, kidney exchange and min-cost flow. Some problems on this site fight you to the bitter end; this one simply yields — and in yielding, quietly pairs the world: applicants to jobs, riders to drivers, donors to patients, as well as the connections will allow.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/max-matching/Content licensed under CC BY-NC 4.0.