Graph and optimization models for kidney exchanges

Nowadays, the preferred treatment option offered to patients with an end-stage renal disease is to receive a kidney transplant from a living donor. This option is primarily used when the patient has a relative who is willing to donate a healthy kidney. However, in many situations, the transplantation cannot take place due to immunological incompatibility between the patient and the healthy donor.
Kidney exchange programs (KEPs) try to alleviate this limitation by enlisting a large number of incompatible patient-donor pairs (P_i,D_i), each one made up of a patient P_i and a donor D_i, where P_i is incompatible with D_i but P_i is typically compatible with a few donors D_k different from D_i. Considering such a pool makes it potentially feasible to perform sequences of transplantations in cyclic fashion across several pairs.
Kidney exchange programs typically try to maximize the number of cyclic exchanges performed in the pool by matching as many compatible individuals as possible. This optimization problem can be modeled as the problem of covering a maximum number of vertices of a compatibility digraph G = (V,A) by disjoint cycles, where V is the set of patient-donor pairs and there is an arc from pair k to pair i if the donor of pair k is compatible with the patient of pair i.
In this talk, I present some recent contributions on different models obtained by introducing uncertainty or stability considerations into the basic kidney exchange model. In particular, I show how these models lead to new graph theoretic concepts and optimization problems.
The talk is based on joint work with Marie Baratto, Valentin Bartier, João Pedro Pedroso, Bart Smeulders, Frits Spieksma and Ana Viana.