Parameterized Algorithms for Kidney Exchange
Abstract
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 l_c and l_p respectively that covers at least some specific number t of non-altruistic 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{l_p, l_c}, and (3) the number of vertex types in the input graph when l_p <= l_c. 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.
BibTeX
@inproceedings{ijcai2022p58,
title = {Parameterized Algorithms for Kidney Exchange},
author = {Maiti, Arnab and Dey, Palash},
booktitle = {Proceedings of the Thirty-First International Joint Conference on
Artificial Intelligence, {IJCAI-22}},
publisher = {International Joint Conferences on Artificial Intelligence Organization},
editor = {Lud De Raedt},
pages = {405--411},
year = {2022},
month = {7},
note = {Main Track},
doi = {10.24963/ijcai.2022/58},
url = {https://doi.org/10.24963/ijcai.2022/58},
}