Is there an algorithm to represent how a "kidney exchange chain" works?

5    23 Jul 2015 16:07 by u/CollateralFortune

I need to replicate the essentials of this for a project and I'm having problems wrapping my brain around it. Every attempt I make at it just gets silly.

For example:

A needs a kidney, and their brother B has one to donate, but they aren't compatible. C needs B's kidney, but B isn't going to give it up until you find A a kidney. In this scenario, nobody gets a kidney.

D comes along and has a kidney that A can use, and donates it out of the goodness of his/her heart. The chain is complete.

Now imagine you have thousands of needs/has available, and you have to build the shortest path between them. That's my problem.

4 comments

2 u/CaptainParanoia 23 Jul 2015 17:37

You can model it as a directed graph, your edges are compatible donations (donor -> patient) and family relations (patient -> family member). People who donate and don't want anything in return have incoming edges from all patients.

Then you can pick a patient A and use Dijkstra's algorithm to find the shortest path A -> A. That should give you a chain of trades.

0 u/SelfReferenceParadox 23 Jul 2015 17:19

Just off the top of my head, it sounds to me like this may reduce to the Travelling Salesman Problem, making this a very difficult problem to solve for large data sets, like you wanted. If you're OK with getting a non-optimal answer, some kind of heuristic.

0 u/CaptainParanoia 23 Jul 2015 17:26

Not quite, TSP visits all nodes. And there is software like CONCORDE that can handle very large instances.

0 u/randrews 24 Jul 2015 06:07

D only donates the kidney if B agrees to donate his though, right? Because otherwise it's really simple and C is left screwed.