The kidney exchange problem: length-constrained cycles and chains optimization on compatibility graphs.

Abstract: The kidney exchange problem is a combinatorial optimization problem that arises naturally when implementing centralized kidney exchange programs. Given a directed weighted graph (called the compatibility graph), we aim to find a collection of simple and vertex-disjoint cycles maximizing the total weight of their participating arcs.

Because of logistical considerations, a bound k is placed on the length of each possible cycle. We will briefly explain how the problem is polynomially solvable in the cases k = 2 and unbounded k, and why it turns NP-complete for k >= 3.

MIP formulations are used in practice because of their efficiency and flexibility to accommodate extra constraints of the exchange programs. We will introduce the cycles MIP formulation of Roth et al. and explain why its linear relaxation is polynomially solvable. Inspired by this result, we present a conjecture on the integrality gap of this formulation, which is part of our ongoing work.

Time permitting, we will also discuss the addition of exchange chains starting from a distinguished subset of vertices (representing deceased or altruistic donors) and explain how their introduction makes even the associated linear relaxation problem NP-hard.