The Math of Organ Donation: Kidneys are an NP-hard Problem

We’re bilaterally symmetric organisms—we’ve got matching bits on our left and right side. But many critical organs are present in only a single copy (hello heart) or we need both to function optimally (see: lungs). The kidneys are rare exceptions, as your body gets by just fine with only a single one. That has enabled people to become living kidney donors, with both the donor and recipient continuing life with one kidney.

Often, in cases where someone needs a transplant, there is a relative willing to make this sacrifice, but unable to do so because they aren’t a close enough tissue match, which would lead to the organ’s rejection by its new host’s immune system. Separately, there are some rare individuals who are simply willing to donate a kidney to an unknown recipient. So the medical community has started doing “donation chains,” where a group of donor-recipient pairs are matched so that everyone who receives a kidney has a paired donor that gives one to someone else.

That, as it turns out, has created its own problem: given a large pool of donors and recipients, how do you pull a set of optimized donor chains out? It turns out that the optimization belongs to a set of mathematical problems that are called NP-hard, making them extremely difficult to calculate as the length of the chain goes up. But now, some researchers have developed algorithms that can solve the typical challenges faced by hospitals with the processing power of a desktop computer.

Source: The math of organ donation: kidneys are an NP-hard problem

This is an article for why you did that math in high school/post-secondary 😉