International Kidney Exchange
Lead Research Organisation:
Durham University
Department Name: Computer Science
Abstract
Description:
This PhD project lies in the intersection area of Computer Science, Economics and Mathematics.
Background.
Many people suffer from chronic kidney disease, which can lead to end stage renal failure (ESRF). ESRF can have a devastating impact on patients' lives. The most common treatment is dialysis. However, dialysis presents major health and lifestyle challenges for patients. On the other hand, kidney transplantation is a much more effective treatment that yields a longer life expectancy of patients. Kidney Exchange Programmes (KEPs) allow patients who require a kidney transplant, and who have a willing but medically incompatible donor, to "swap" their donor with that of another patient. This leads to a cycle of kidney transplants in which all patients obtain a compatible kidney.
The Model.
One can model a pool of patient-donor pairs as a directed graph G = (V, A) (the compatibility graph), in which the set V consists of nodes representing the patient-donor pairs, and the set A consists of every arc (u,v) such that the donor of node u is compatible with the patient of node v. A k-way exchange cycle in G is a directed cycle with k arcs that can be used for kidney transplants. For example, a 3-way exchange cycle in G is a cycle with arcs (u,v), (v,w) and (w,u) such that the kidney of the donor of node u could be given to the patient of node v; the kidney of the donor of node v could be given to the patient of node w; and the kidney of the donor of node w could be given to the patient of node u.
To prevent exchange cycles from breaking (and a patient from losing their willing donor), hospitals perform the k kidney transplants in a k-way exchange simultaneously. Hence, KEPs impose a bound p (the exchange bound) on the maximum length of an exchange cycle, typically p is set between 2 and 5. A p-cycle packing of a compatibility graph G is a set C of pairwise vertex-disjoint directed cycles, each having at most p arcs. An optimal solution is a p-cycle packing that covers as many nodes of G as possible.
Computability graphs are constructed by KEPS in regular rounds, and in each round an optimal solution must be computed. If p=2, then we can find an optimal solution in polynomial time by solving a maximum matching problem. However, if p>2, then this problem is computationally hard.
The Objectives.
The demand for available kidneys consistently exceeds supply, and the project therefore has the following two main objectives.
1. The first objective of the project is to deal with the aforementioned computational hardness if the exchange bound p is realistically set between 3 and 5. The project will consider the research question: to what extent can the structure of the computability graphs be exploited in order to obtain efficient algorithms for finding optimal solutions?
2. The second objective of the project is related to the international setting, in which various countries merge their national pools of patient-donor pairs. In this way better solutions can be obtained, helping more patients overall. However, countries may withdraw from an international KEP if they believe they could obtain more kidney transplants on their own or with a smaller group of countries. As such, the project will also consider the research question: how can we ensure that an international KEP stays stable in the long term? The project will study computational complexity aspects of using credit-based systems, where countries disadvantaged in one round are compensated in a next round.
This PhD project lies in the intersection area of Computer Science, Economics and Mathematics.
Background.
Many people suffer from chronic kidney disease, which can lead to end stage renal failure (ESRF). ESRF can have a devastating impact on patients' lives. The most common treatment is dialysis. However, dialysis presents major health and lifestyle challenges for patients. On the other hand, kidney transplantation is a much more effective treatment that yields a longer life expectancy of patients. Kidney Exchange Programmes (KEPs) allow patients who require a kidney transplant, and who have a willing but medically incompatible donor, to "swap" their donor with that of another patient. This leads to a cycle of kidney transplants in which all patients obtain a compatible kidney.
The Model.
One can model a pool of patient-donor pairs as a directed graph G = (V, A) (the compatibility graph), in which the set V consists of nodes representing the patient-donor pairs, and the set A consists of every arc (u,v) such that the donor of node u is compatible with the patient of node v. A k-way exchange cycle in G is a directed cycle with k arcs that can be used for kidney transplants. For example, a 3-way exchange cycle in G is a cycle with arcs (u,v), (v,w) and (w,u) such that the kidney of the donor of node u could be given to the patient of node v; the kidney of the donor of node v could be given to the patient of node w; and the kidney of the donor of node w could be given to the patient of node u.
To prevent exchange cycles from breaking (and a patient from losing their willing donor), hospitals perform the k kidney transplants in a k-way exchange simultaneously. Hence, KEPs impose a bound p (the exchange bound) on the maximum length of an exchange cycle, typically p is set between 2 and 5. A p-cycle packing of a compatibility graph G is a set C of pairwise vertex-disjoint directed cycles, each having at most p arcs. An optimal solution is a p-cycle packing that covers as many nodes of G as possible.
Computability graphs are constructed by KEPS in regular rounds, and in each round an optimal solution must be computed. If p=2, then we can find an optimal solution in polynomial time by solving a maximum matching problem. However, if p>2, then this problem is computationally hard.
The Objectives.
The demand for available kidneys consistently exceeds supply, and the project therefore has the following two main objectives.
1. The first objective of the project is to deal with the aforementioned computational hardness if the exchange bound p is realistically set between 3 and 5. The project will consider the research question: to what extent can the structure of the computability graphs be exploited in order to obtain efficient algorithms for finding optimal solutions?
2. The second objective of the project is related to the international setting, in which various countries merge their national pools of patient-donor pairs. In this way better solutions can be obtained, helping more patients overall. However, countries may withdraw from an international KEP if they believe they could obtain more kidney transplants on their own or with a smaller group of countries. As such, the project will also consider the research question: how can we ensure that an international KEP stays stable in the long term? The project will study computational complexity aspects of using credit-based systems, where countries disadvantaged in one round are compensated in a next round.
Organisations
People |
ORCID iD |
Daniel Paulusma (Primary Supervisor) | |
Yilin Li (Student) |
Studentship Projects
Project Reference | Relationship | Related To | Start | End | Student Name |
---|---|---|---|---|---|
EP/W524426/1 | 30/09/2022 | 29/09/2028 | |||
2919588 | Studentship | EP/W524426/1 | 30/09/2024 | 30/03/2028 | Yilin Li |