# Randomized Parameterized Algorithms for the Kidney Exchange Problem
## 1 Introduction  
Kidney transplantation is one of the best treatment methods for those who are suffering from end-stage renal failure. Unfortunately, it is quite difficult for some patients to find suitable kidneys because of a lack of deceased donors and incompatibility of their blood and tissue types with willing donors. Although some patients can buy living donor kidneys from marketplaces, it is commonly considered to be unethical to commercialize of human organs. Moreover, it is in fact illegal in most countries. Living donation is regarded as legal as long as it occurs as a gift instead of a commodity to make profit. But it often arises that a donor who in general is a relative or friend of a patient is willing to donate a kidney to the patient even though their kidneys are not physiologically compatible such that the kidney transplantation cannot be carried out. Therefore, it is a significant research topic to effectively utilize living-donor kidneys such that their incompatible intended recipients can obtain one compatible kidney from these living-donor kidneys by exchanging. In 1986, [PERSON] [1] first presented the idea of kidney paired donation where two incompatible patient-donor pairs reciprocally exchange the donors' kidneys so that two patients respectively obtain a compatible kidney, where an incompatible patient-donor pair represents a patient and his willing but incompatible donor. Since then, kidney exchange programs have developed rapidly and have already been established in some countries, for example, the USA, the UK, Turkey, Switzerland, and South Korea [2]. The Kidney Exchange problem (KEP) is the central issue of kidney exchange programs from a computational point of view. In a set of incompatible patient-donor pairs, the KEP is to find the exchanges with the maximum collective benefit such that each patient-donor pair of the exchanges can donate a kidney to some pair and receive a compatible kidney from another pair. The collective benefit is usually measured by the total number of possible kidney transplants [3; 4; 5; 6; 7; 8]. From a graph theory perspective, as a type of barter exchange, kidney exchange is implemented by cycles comprising patient-donor pairs, where each donor in a pair donates a kidney to the patient in the next pair. Theoretically speaking, long cycle exchanges are better, since they are beneficial in improving the chances that more incompatible pairs are contained into the exchanges. However, the length of cycles must be limited in a certain range for the following reasons. First, to ensure an exchange cycle is executed successfully, all operations should be performed simultaneously so as to reduce the risk that a donor might break his promise after his incompatible patient has obtained a kidney before he donates his kidney. Long cycle exchanges may bring substantial logistical difficulties because the number of personnel and facilities required for simultaneous operations is too large. Second, all exchanges of a cycle will be cancelled if the final crossmatch test before operations detects new incompatibilities. Hence, longer cycles may cause greater logistical complexity and greater exchange failure risk. As a result, the length of cycles is generally limited in the range \([2,L]\), where \(L\) is a given constant and usually \(2\leq L\leq 5\). Therefore, the KEP can be regarded as finding an optimal packing of vertex-disjoint cycles from a given directed graph such that the length of each cycle is at most \(L\). When considering altruistic donors, kidney exchange allows the inclusion of chains which start from altruistic donors and end with either a pair or a patient in a wait list. The KEP becomes more complex, and can be modelled as finding an optimal set of vertex-disjoint cycles and chains from the directed graph of given instance such that the length of each cycle is at most \(L\)[5].