The Chain That Saves Lives

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.

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">{{hint}}</p>
<div id="pairs" class="pairs"></div>
<h4 class="h">{{poss_exchanges}}</h4>
<div id="cands" class="cands"></div>
<div class="meter">
  <div>{{transplants_label}}: <b id="count" class="g">0</b> / 6</div>
  <div id="msg" class="msg"></div>
</div>
<div class="btns">
  <button id="opt" type="button">{{btn_optimize}}</button>
  <button id="reset" type="button" class="ghost">{{btn_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; }

// Code not found

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.

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.

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.

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.