Parameterized Algorithms for Kidney Exchange

In kidney exchange programs, multiple patient-donor pairs each of whom are otherwise incompatible, exchange their donors to receive compatible kidneys. The Kidney Exchange problem is typically modelled as a directed graph where every vertex is either an altruistic donor or a pair of patient and donor; directed edges are added from a donor to its compatible patients. The computational task is to find if there exists a collection of disjoint cycles and paths starting from altruistic donor vertices of length at most ℓ𝑐 and ℓ𝑝 respectively that covers at least some specific number 𝑡 of nonaltruistic vertices (patients). We study parameterized algorithms for the kidney exchange problem in this paper. Specifically, we design FPT algorithms parameterized by each of the following parameters: (1) the number of patients who receive kidney, (2) treewidth of the input graph + max{ℓ𝑝, ℓ𝑐 }, and (3) the number of vertex types in the input graph when ℓ𝑝 ≤ ℓ𝑐. We also present interesting algorithmic and hardness results on the kernelization complexity of the problem. Finally, we present an approximation algorithm for an important special case of Kidney Exchange.

Authors

• Arnab Maiti University of Washington
• Palash Dey

Keywords

• Fixed-Parameter Tractability
• Kidney Exchange
• Vertex Type
• Kernelization
• Altruistic donors
• Compatibility graph
• Tradingcycle
• Trading-chain