Computing at Glasgow University
Paper ID: 9318

Maximum weight cycle packing in directed graphs, with application to kidney exchange programs
Biro,P. Manlove,D.F. Rizzi,R.

Publication Type: Journal
Appeared in: Discrete Mathematics, Algorithms and Applications, volume 1, number 4
Page Numbers : 499-517
Publisher: World Scientific
Year: 2009

URL: This publication is available at this URL.


Centralised matching programs have been established in several countries to organise kidney exchanges between incompatible patient-donor pairs. At the heart of these programs are algorithms to solve kidney exchange problems, which can be modelled as cycle packing problems in a directed graph, involving cycles of length 2, 3, or even longer. Usually the goal is to maximise the number of transplants, but sometimes the total benefit is maximised by considering the differences between suitable kidneys. These problems correspond to computing cycle packings of maximum size or maximum weight in directed graphs. Here we prove the APX-completeness of the problem of finding a maximum size exchange involving only 2-cycles and 3-cycles. We also present an approximation algorithm and an exact algorithm for the problem of finding a maximum weight exchange involving cycles of bounded length. The exact algorithm has been used to provide optimal solutions to real kidney exchange problems arising from the National Matching Scheme for Paired Donation run by NHS Blood and Transplant, and we describe practical experience based on this collaboration.

Keywords: Living kidney donation; Optimal exchange; APX-completeness; Approximation algorithm; Exact algorithm; NHS Blood and Transplant

PDF Bibtex entry Endnote XML