Parameterized Complexity of Kidney Exchange Revisited

Úrsula Hébert-Johnson, Daniel Lokshtanov, Chinmay Sonar, Vaishali SurianarayananIJCAI 2024

Introduction

The Kidney Exchange Problem (KEP) is a critical optimization challenge in healthcare, where patient-donor pairs are matched to facilitate life-saving transplants. Formally, KEP is modeled as finding a collection of vertex-disjoint cycles and paths in a directed graph to maximize the total number of vertices (patients) covered. While the general problem is NP-hard, recent research has focused on identifying parameters that make the problem tractable. This paper addresses three key parameters: the number of vertex types ($\theta$), the treewidth of the compatibility graph ($\omega$), and the target number of patients helped ($t$).

Methodology and Theoretical Framework

Vertex Types ($\theta$) and Succinct Representations

The authors investigate the complexity of KEP when the number of vertex types—groups of individuals with identical compatibility profiles—is small. They employ an Integer Linear Programming (ILP) approach based on a "quotient graph" representation. The core insight is that any optimal solution can be represented succinctly using a limited number of configuration graphs.

Mathematical formulation of derived graphs used in the succinctness proof.

By proving that any solution can be decomposed into these derived configurations (as shown in the summation above), they bound the number of variables in the ILP by a function of $\theta$, proving that the problem is Fixed-Parameter Tractable (FPT) with respect to this parameter.

Algebraic Algorithms for Target Size ($t$)

To determine if at least $t$ patients can be helped, the authors utilize advanced algebraic techniques. They construct a formal polynomial where terms correspond to potential donation plans. A randomized algorithm then detects multilinear terms (representing valid vertex-disjoint exchanges) using the Isolation Lemma. This approach significantly improves the efficiency of finding solutions of a specific size.

Hardness for Treewidth ($\omega$)

Treewidth is a common parameter used to solve hard graph problems. However, the authors demonstrate that KEP remains computationally difficult even for graphs with low treewidth. By performing a hardness reduction from the Multicolored Clique problem, they establish that KEP is W[1]-hard with respect to $\omega$. This result suggests that the global constraints of vertex-disjointness in KEP are fundamentally incompatible with standard treewidth-based FPT techniques.

Key Results and Contributions

The paper provides definitive answers to several open questions in the field:

  • Resolution of Open Problems: It settles two long-standing questions regarding the complexity of KEP under treewidth and vertex type parameters.
  • Algorithmic Breakthrough: The randomized algorithm for the parameter $t$ achieves a running time of $4^t \cdot n^{O(1)}$, a dramatic improvement over the previous $161^t \cdot n^{O(1)}$ bound.
  • Complexity Boundaries: The W[1]-hardness proof for treewidth defines a clear boundary for algorithmic search, shifting focus toward approximation schemes for tree-like graphs.

Discussion and Future Directions

While the $4^t$ algorithm is a major leap, its randomized nature presents a trade-off; the deterministic variant is slower ($14.34^t$). Future work may focus on closing this gap. Additionally, the high tower of exponents in the ILP for vertex types suggests that a single-exponential FPT algorithm remains a significant "holy grail" for the community. Finally, the hardness result for treewidth motivates the development of efficient approximation algorithms for graphs with restricted structural complexity.

Summary updated

BibTeX
@inproceedings{hebertjohnson2024parameterized,
  author = {Úrsula Hébert-Johnson and Daniel Lokshtanov and Chinmay Sonar and Vaishali Surianarayanan},
  title = {{Parameterized Complexity of Kidney Exchange Revisited}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2024},
}
Figure