Introduction

Someone you love needs a kidney. You volunteer — and then the news lands: you're not compatible. Your kidney can't go to them. It's heartbreaking, and it's common.

But here's the idea that changes everything. Somewhere there's another pair in exactly the same bind: a willing donor who can't help their own patient — but can help yours, while your donor can help theirs. Swap the donors and both patients get a transplant. That's a 2-way exchange. Extend it to three pairs in a ring, or a long chain kicked off by an altruistic donor, and a single arrangement can save many lives at once.

The puzzle is choosing which swaps to make. With dozens or thousands of pairs, the compatible cycles overlap and compete — pick the wrong ones and fewer people get transplants. This is kidney exchange, one of the most consequential hard problems on this site: its math is NP-hard, its design won a Nobel Prize, and its answers are measured in lives.

Build the Chain

Try it. Six donor-patient pairs are stuck — each donor is incompatible with their own patient. Below are the possible exchanges their compatibilities allow (2-way swaps and one 3-way cycle). Click to add an exchange to your plan; you can't reuse a pair, so choosing one swap may rule out another.

<p class="hint">Six donor–patient pairs, each internally incompatible. Their compatibilities allow the <b>exchanges</b> below. Click to add one to your plan — but a pair can only be in <b>one</b> exchange. Maximize <span class="g">transplants</span>, then Optimize.</p>
<div id="pairs" class="pairs"></div>
<h4 class="h">Possible exchanges</h4>
<div id="cands" class="cands"></div>
<div class="meter">
  <div>Transplants: <b id="count" class="g">0</b> / 6</div>
  <div id="msg" class="msg"></div>
</div>
<div class="btns">
  <button id="opt" type="button">Optimize</button>
  <button id="reset" type="button" class="ghost">Reset</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 .8rem; line-height: 1.45; }
.hint .g { color: #0a7d33; font-weight: 700; }
.pairs { display: grid; grid-template-columns: repeat(6, 1fr); gap: .4rem; margin-bottom: .9rem; }
.pair { text-align: center; border: 2px solid #e2e6eb; border-radius: 8px; padding: .4rem .2rem; font: 700 13px system-ui; color: #555; background: #fff; }
.pair.on { border-color: #0a7d33; background: #e6f6ec; color: #0a7d33; }
.pair small { display: block; font-weight: 500; font-size: .8em; color: #999; }
.h { font: 700 13px system-ui; color: #1d3557; margin: .2rem 0 .5rem; }
.cands { display: flex; flex-direction: column; gap: .5rem; margin-bottom: .9rem; }
.cand { border: 2px solid #457b9d; border-radius: 8px; padding: .5rem .7rem; cursor: pointer; display: flex; justify-content: space-between; align-items: center; font: 600 14px system-ui; color: #1d3557; background: #fff; }
.cand:hover { background: #f0f4f8; }
.cand.sel { background: #457b9d; color: #fff; border-color: #457b9d; }
.cand.blocked { opacity: .4; cursor: not-allowed; border-color: #ccc; color: #999; }
.cand .badge { font: 700 12px system-ui; background: rgba(0,0,0,.08); border-radius: 99px; padding: .1rem .5rem; }
.cand.sel .badge { background: rgba(255,255,255,.25); }
.meter { display: flex; gap: 1.4rem; align-items: center; font-size: 1rem; margin-bottom: .7rem; flex-wrap: wrap; }
.meter .g { color: #0a7d33; }
.msg { font-weight: 700; color: #0a7d33; }
.btns { display: flex; gap: .5rem; }
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] ?? ''));
// Kidney exchange: pick disjoint compatible cycles to maximize transplants.
// NP-hard with cycle-length limits. Greedy "biggest cycle first" is a trap:
// grabbing the 3-way here blocks a pair and yields only 5 of 6.
const PAIRS = ['P1', 'P2', 'P3', 'P4', 'P5', 'P6'];
// each exchange: label, member pair indices (its size = transplants it gives)
const CANDS = [
  { label: 'P1 ⇄ P2', members: [0, 1] },
  { label: 'P3 ⇄ P4', members: [2, 3] },
  { label: 'P5 ⇄ P6', members: [4, 5] },
  { label: 'P3 → P4 → P5 (3-way)', members: [2, 3, 4] }
];
const OPT = 6; // P1⇄P2 + P3⇄P4 + P5⇄P6 covers everyone
let chosen;

function reset() { chosen = []; render(); }

function covered(set) { const s = new Set(); set.forEach(ci => CANDS[ci].members.forEach(m => s.add(m))); return s; }
function conflicts(ci, set) {
  const cov = covered(set);
  return CANDS[ci].members.some(m => cov.has(m));
}

function toggle(ci) {
  const i = chosen.indexOf(ci);
  if (i >= 0) { chosen.splice(i, 1); render(); return; }
  if (conflicts(ci, chosen)) return; // blocked
  chosen.push(ci); render();
}

function render() {
  const cov = covered(chosen);
  document.getElementById('pairs').innerHTML = PAIRS.map((p, i) =>
    '<div class="pair' + (cov.has(i) ? ' on' : '') + '">' + p + '<small>' + (cov.has(i) ? '✓' : '—') + '</small></div>').join('');
  document.getElementById('cands').innerHTML = CANDS.map((c, ci) => {
    const sel = chosen.includes(ci);
    const blocked = !sel && conflicts(ci, chosen);
    const cls = sel ? ' sel' : (blocked ? ' blocked' : '');
    return '<div class="cand' + cls + '" data-ci="' + ci + '"><span>' + c.label +
      '</span><span class="badge">+' + c.members.length + '</span></div>';
  }).join('');
  document.querySelectorAll('.cand').forEach(el => el.addEventListener('click', () => toggle(+el.dataset.ci)));
  const n = cov.size;
  document.getElementById('count').textContent = n;
  const m = document.getElementById('msg');
  if (n === OPT) { m.style.color = '#0a7d33'; m.textContent = '✓ Everyone transplanted — optimal!'; }
  else if (chosen.includes(3)) { m.style.color = '#b9770e'; m.textContent = 'The 3-way looks big, but it strands a pair. Try three 2-way swaps.'; }
  else { m.style.color = '#777'; m.textContent = fmt('%n% of 6 so far.', { n: n }); }
}

// Optimize: brute-force the best disjoint set of exchanges (max transplants).
function optimize() {
  let best = [], bestN = 0;
  for (let mask = 0; mask < (1 << CANDS.length); mask++) {
    const set = [], seen = new Set(); let ok = true;
    for (let ci = 0; ci < CANDS.length; ci++) if (mask & (1 << ci)) {
      for (const m of CANDS[ci].members) { if (seen.has(m)) { ok = false; break; } seen.add(m); }
      if (!ok) break; set.push(ci);
    }
    if (ok && seen.size > bestN) { bestN = seen.size; best = set; }
  }
  chosen = best; render();
}

document.getElementById('opt').addEventListener('click', optimize);
document.getElementById('reset').addEventListener('click', reset);
reset();
Result
Console

Maximize the transplants. Then hit Optimize. Watch out: grabbing the biggest cycle first — the tempting 3-way — can actually leave fewer people transplanted than three careful 2-way swaps. That trap is exactly why this needs real optimization.

The Hard Part

Why is choosing the swaps so hard?

  • Checking a plan is easy: confirm every exchange is compatible and no pair appears twice, then count transplants.
  • It's a cycle cover. Build a directed graph: an arrow from pair X to pair Y means X's donor can give to Y's patient. A valid exchange is a cycle, and we want disjoint cycles covering as many pairs as possible.
  • Length limits make it NP-hard. With unbounded cycles the problem is easy — but real transplants in a cycle must happen simultaneously (so no donor backs out after their patient is helped), which caps cycle length to 2 or 3. Maximizing transplants under that cap is NP-hard.
  • Greedy fails. As the demo shows, taking the largest cycle first can block better combinations. Optimization, not intuition, is required.
  • Practice uses integer programming. Real programs (UNOS in the US, the UK and others) run ILP solvers over the whole pool, plus chains started by altruistic donors — which needn't be simultaneous, so they can be long and unlock many transplants.

It's a matching problem with a brutal twist: the constraints that keep it ethical and safe are exactly what make it computationally hard.

Where It Matters

The stakes here are unusually literal:

  • Kidney paired donation: national programs match thousands of otherwise-stuck pairs every year, dramatically expanding living-donor transplants.
  • Altruistic-donor chains: a single non-directed donor can trigger a chain that helps dozens of patients down the line.
  • Nobel-winning market design: the theory of matching markets (Roth, Shapley) turned this from idea into life-saving infrastructure.
  • Beyond organs: the same matching ideas allocate students to schools, residents to hospitals, and shared resources fairly.

Few algorithms have a clearer payoff: better optimization means more transplants, shorter waits, and lives saved.

Conclusion

Kidney exchange is where the abstract becomes urgent. The same combinatorial difficulty that makes scheduling and packing hard shows up here as a directed-cycle cover with length limits — but the objective isn't cost or waste, it's people who get to live.

What's moving is that mathematicians and economists didn't just prove it hard; they built the solvers and the markets that make it work, every day, in real hospitals. It's the strongest possible answer to "why study hard problems": sometimes the right algorithm is the difference between a transplant and a tragedy.

Share this article

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

Comments

Loading comments...

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