Parameterized Complexity of Kidney Exchange Revisited

As of January 2023, there are more than 90, 000 people on the national transplant waiting list in need of a kidney in the United States. These patients often have a friend or family member who is willing to donate, but whose kidney type might not be compatible. To help match these patients to suitable donors, patient-donor compatibility can be modeled as a directed graph. Specifically, in the Kidney Exchange problem, the input is a directed graph G, a subset B of vertices (altruistic donors), and two integers lₚ and lc. An altruistic donor is a donor who is not paired with a patient, and the remaining vertices are patient-donor pairs. Whenever a donor is compatible with a patient from a patient-donor pair, we place a directed edge from the donor vertex to the patient-donor pair. Here the donor vertex can be either altruistic or non-altruistic. The goal is to find a collection of vertex-disjoint cycles and paths covering the maximum number of patients such that each cycle has length at most lc, and such that each path has length at most lₚ and begins at a vertex in B. The path and cycle lengths are bounded so that the surgeries for a given path or cycle can be performed simultaneously. Kidney Exchange has received a great deal of attention in recent years. We contribute to this line of work by closing two open problems from IJCAI '18 and IJCAI '22: "Is Kidney Exchange FPT when parameterized by (i) the treewidth (omega) of G and (ii) the number of vertex types in G? '' Two vertices have the same vertex type if they have the same in- and out-neighborhoods. We show that Kidney Exchange is FPT parameterized by the number of vertex types. On the other hand, we show W1-hardness with respect to omega. We also design a randomized 4ᵗ * nO (1) -time algorithm parameterized by t, the number of patients helped, significantly improving upon the previous state of the art, which was 161ᵗ * nO (1).