Exact Algorithms and Complexity of Kidney Exchange

Mingyu Xiao, Xuanbei WangIJCAI 2018 · DOI

TL;DR

This paper presents novel exact algorithms for the kidney exchange problem, a crucial task in organ transplantation. They achieve a single-exponential time complexity for the general problem with length constraints and a fixed-parameter tractable (FPT) algorithm for the unconstrained version, significantly improving upon previous theoretical bounds.

What Problem Does This Paper Address?

Kidney exchange is a vital strategy to overcome the shortage of compatible donor kidneys. It involves patients with incompatible donors swapping kidneys to find a suitable match. The core computational challenge lies in finding the optimal way to arrange these swaps, which can be modeled as finding the largest set of vertex-disjoint cycles and chains in a compatibility graph. This problem is NP-hard. Real-world constraints, such as limited human resources for surgeries, often restrict the length of these cycles and chains. This paper tackles two main versions of this problem: one with explicit upper bounds on cycle and chain lengths, and another with no length constraints (the "free version"). The goal is to maximize the number of patients who receive a life-saving kidney.

Methods

The authors employ two primary algorithmic techniques:

  • Dynamic Programming and Subset Convolution: For the general kidney exchange problem with length constraints ($(L_c, L_p)$-KEP), they develop an exact algorithm with a single-exponential running time of $O(2^n n^3)$. This is achieved by first using dynamic programming to identify all possible "packing units" (cycles or chains meeting the length criteria) within any subset of vertices. Subsequently, they leverage subset convolution, a powerful technique for combining information across all subsets, to find the optimal disjoint packing of these units. This approach is a significant improvement over previous algorithms that relied on integer programming or had much worse running time bounds.
  • Decomposition Technique and Integer Programming (IP): For the free version of the kidney exchange problem (F-KEP), they introduce a fixed-parameter tractable (FPT) algorithm parameterized by the number of "vertex types" ($\theta$). Vertices are classified into types based on their neighborhood properties. The algorithm first constructs a "quotient graph" by grouping vertices of the same type. Then, it formulates an integer programming problem on this quotient graph to determine the optimal number of vertices to include from each type. Finally, a decomposition technique is used to translate the IP solution back into a concrete cycle/chain packing in the original graph. This FPT algorithm implies that F-KEP can be solved in polynomial time if the number of vertex types is bounded by a constant.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Subset Convolution as a Powerful Tool: The paper demonstrates the effectiveness of subset convolution for solving combinatorial optimization problems on graphs, specifically for finding optimal packings of cycles and chains. This technique allows for efficient aggregation of information across all possible subsets of vertices.
  • "Vertex Types" as a Key Parameter: The introduction of "vertex types" as a parameter for F-KEP is a crucial insight. It allows for a more structured approach to the problem, leading to an FPT algorithm. This concept is inspired by real-world observations that patients and donors often share similar characteristics (blood type, age, etc.), leading to predictable neighborhood structures in the compatibility graph.
  • Unified Framework for Variants: The authors highlight that their dynamic programming and subset convolution framework for $(L_c, L_p)$-KEP can be adapted to solve other variants of the kidney exchange problem with similar running time bounds.
  • Theoretical Improvement: The paper provides a significant theoretical advancement by establishing single-exponential time complexity for the general problem and an FPT algorithm for the unconstrained version, pushing the boundaries of what is computationally feasible for this important problem.

Key Results

  • Exact Algorithm for $(L_c, L_p)$-KEP: An exact algorithm with a running time of $O(2^n n^3)$ is presented, which is single-exponential in the number of vertices ($n$). This is a substantial improvement over previous theoretical bounds.
  • FPT Algorithm for F-KEP: An FPT algorithm for the free version of kidney exchange is developed, parameterized by the number of vertex types ($\theta$). This means the problem can be solved efficiently if the number of distinct vertex types is small.

Limitations and Future Work

  • Theoretical Focus: The algorithms presented are theoretical exact algorithms. Their practical performance on large, real-world kidney exchange instances is not evaluated in this paper. Future work could involve implementing these algorithms and comparing them to existing heuristic or approximation methods.
  • Realistic Constraints: While the paper addresses length constraints, other real-world factors like compatibility scores, fairness considerations, and the cost of surgeries are not explicitly modeled. Extending the algorithms to incorporate these aspects would be a valuable direction.
  • Further Exploration of Quotient Graphs: The paper introduces the concept of quotient graphs for F-KEP. Further research could explore the properties of these quotient graphs and their application to other graph-based optimization problems.

Summary updated

BibTeX
@inproceedings{xiao2018exact,
  author = {Mingyu Xiao and Xuanbei Wang},
  title = {{Exact Algorithms and Complexity of Kidney Exchange}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2018},
  doi = {10.24963/ijcai.2018/77},
}
Figure