A Faster Deterministic Algorithm for Kidney Exchange via Representative Set

摘要

The Kidney Exchange Problem is a prominent challenge in healthcare and economics, arising in the context of organ transplantation. It has been extensively studied in artificial intelligence and optimization. In a kidney exchange, a set of donor-recipient pairs and altruistic donors are considered, with the goal of identifying a sequence of exchanges—comprising cycles or chains starting from altruistic donors—such that each donor provides a kidney to the compatible recipient in the next donor-recipient pair. These exchanges create a network of transplants aimed at maximizing the total number, t, of successful transplants. Due to constraints in medical resources, limits are often imposed on the lengths of these cycles and chains. Recently, this problem was deterministically solved in O* (14.34ᵗ) time (IJCAI 2024). In this paper, we introduce the representative set technique for the Kidney Exchange Problem, showing that the problem can be deterministically solved in O* (6.855ᵗ) time.