No Access

MAXIMUM WEIGHT CYCLE PACKING IN DIRECTED GRAPHS, WITH APPLICATION TO KIDNEY EXCHANGE PROGRAMS

PÉTER BIRÓ

Department of Computing Science, University of Glasgow, Glasgow, G12 8QQ, UK

Supported by EPSRC grant EP/E011993/1.

Supported by OTKA grant K69027.

Search for more papers by this author

DAVID F. MANLOVE

Department of Computing Science, University of Glasgow, Glasgow, G12 8QQ, UK

Supported by EPSRC grant EP/E011993/1.

Search for more papers by this author

, and

ROMEO RIZZI

Dipartimento di Matematica ed Informatica (DIMI), Università di Udine, Italy

Search for more papers by this author

https://doi.org/10.1142/S1793830909000373Cited by:49 (Source: Crossref)

Abstract

Centralized matching programs have been established in several countries to organize 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 maximize the number of transplants, but sometimes the total benefit is maximized 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:

AMSC: 05C70, 05C85, 68Q17, 68Q25, 68R10, 68W25

References

D. J. Abraham, A. Blum and T. Sandholm, Clearing algorithms for barter-exchange markets: enabling nationwide kidney exchanges, Proc. EC '07: the Eighth ACM Conference on Electronic Commerce (ACM, 2007) pp. 295–304. Google Scholar
Alliance for Paired Donation website, http://www.paireddonation.org . Google Scholar
E. M. Arkin and R. Hassin, Math. Oper. Res. 23, 640 (1998), DOI: 10.1287/moor.23.3.640. Crossref, Google Scholar
BBC news website. `Six-way' kidney transplant first (9 April 2008), http://news.bbc.co.uk/1/health/7338437.stm . Google Scholar
P. Berman, A d/2 approximation for maximum weight independent set in d-claw free graphs, Proc. SWAT 2000: the 7th Scandinavian Workshop on Algorithm Theory1851, Lecture Notes in Computer Science (Springer, 2000) pp. 214–219. Google Scholar
P. Biró and K. Cechlárová, Inform. Proc. Lett. 101, 199 (2007). Crossref, Google Scholar
P. Biró, D. F. Manlove and R. Rizzi, Maximum weight cycle packing in optimal kidney exchange programs, Technical report, no. TR-2009-298, University of Glasgow, Department of Computing Science, 2009 . Google Scholar
P. Biró and E. McDermid, Algorithmica (2010). Google Scholar
A. Caprara and R. Rizzi, Inform. Proc. Lett. 84, 175 (2002), DOI: 10.1016/S0020-0190(02)00274-0. Crossref, Google Scholar
K. Cechlárová, T. Fleiner and D. Manlove, The kidney exchange game, in Proc. SOR '05: the 8th International Symposium on Operations Research in Slovenia (2005), pp. 77–83. Technical Report, IM Preprint series A, no. 5/2005, PJ Safárik University, Faculty of Science, Institute of Mathematics, 2005 . Google Scholar
K. Cechlárová and V. Lacko, The kidney exchange game: How hard is to find a donor? Technical report, IM Preprint series A, no. 4/2006, PJ Safárik University, Faculty of Science, Institute of Mathematics, 2006 . Google Scholar
B. Chandra and M. Halldórsson, Greedy local improvement and weighted set packing approximation, Proc. SODA '99: the 10th Annual ACM-SIAM Symposium on Discrete Algorithms (ACM, 1999) pp. 169–176. Google Scholar
Z.-Z. Chen, R. Tanahashi and L. Wang, Discrete Appl. Math. 157, 1640 (2009), DOI: 10.1016/j.dam.2008.11.009. Crossref, Google Scholar
M. Chlebík and J. Chlebíková, Approximating hardness for small occurrence instances of NP-hard problems, Proc. CIAC 2003: the 5th Italian Conference on Algorithms and Complexity2653, Lecture Notes in Computer Science (Springer, 2003) pp. 152–164. Google Scholar
J. Edmonds, J Res. NBS B 69B, 125 (1965). Google Scholar
J. Edmonds, Can. J. Math. 17, 449 (1965). Crossref, Google Scholar
H. Fernau, Parameterized algorithmics: a graph-theoretic approach. Habilitationsschrift, Universität Tübingen, Germany and University of Newcastle, Australia, April 2005, http://www.cs.uu.nl/groups/AD/fernau-habil.pdf . Google Scholar
H. N. Gabow, Data structures for weighted matching and nearest common ancestors with linking, Proc. SODA '90: the 1st Annual ACM-SIAM Symposium on Discrete Algorithms (ACM, 1990) pp. 434–443. Google Scholar
M. R. Garey and D. S. Johnson , Computers and Intractability ( W.H. Freeman and Co. , 1979 ) . Google Scholar
R. Hassin and S. Rubinstein, Discrete Appl. Math. 154, 971 (2006), DOI: 10.1016/j.dam.2005.11.003. Crossref, Google Scholar
C. A. J. Hurkens and A. Schrijver, SIAM J. Discrete Math. 2, 68 (1989), DOI: 10.1137/0402008. Crossref, Google Scholar
R. J. Johnsonet al., Transplantation 86, 1672 (2008), DOI: 10.1097/TP.0b013e3181901a3d. Crossref, Google Scholar
V. Kann, Inform. Proc. Lett. 37, 27 (1991), DOI: 10.1016/0020-0190(91)90246-E. Crossref, Google Scholar
K. M. Keizeret al., Transplant. Proc. 37, 589 (2005), DOI: 10.1016/j.transproceed.2004.12.096. Crossref, Google Scholar
M. de Klerket al., Am. J. Transplant. 5, 2302 (2005), DOI: 10.1111/j.1600-6143.2005.01024.x. Crossref, Google Scholar
J. Y. Kwaket al., Transplant. Proc. 31, 344 (1999), DOI: 10.1016/S0041-1345(98)01655-8. Crossref, Google Scholar
L. Lovász and M. D. Plummer , Matching Theory , Annals of Discrete Mathematics ( North-Holland , 1986 ) . Google Scholar
M. Lucanet al., Transplant. Proc. 35, 933 (2003), DOI: 10.1016/S0041-1345(03)00169-6. Crossref, Google Scholar
M. Lucan, Transplant. Proc. 39, 1371 (2007), DOI: 10.1016/j.transproceed.2007.02.081. Crossref, Google Scholar
G. Manic and Y. Wakabayash, Discrete Math. 308, 1455 (2008), DOI: 10.1016/j.disc.2007.07.100. Crossref, Google Scholar
K. Mehlhorn and S. Naher , LEDA: A Platform for Combinatorial and Geometric Computing ( Cambridge University Press , 1999 ) . Google Scholar
S. Micali and V. V. Vazirani, An $O(\sqrt{|V|} \cdot {|E|})$ algorithm for finding maximum matching in general graphs, Proc. FOCS '80: the 21st Annual IEEE Symposium on Foundations of Computer Science (IEEE Computer Society, 1980) pp. 17–27. Google Scholar
New England Program for Kidney Exchange website, http://www.nepke.org . Google Scholar
Organ Donation and Transplantation Directorate, NHS Blood and Transplant website, http://www.organdonation.nhs.uk . Google Scholar
Paired Donation Network website, http://www.paireddonationnetwork.org . Google Scholar
C. H. Papadimitriou and M. Yannakakis, J. Comput. Syst. Sci. 43, 425 (1991), DOI: 10.1016/0022-0000(91)90023-X. Crossref, Google Scholar
K. Parket al., Transplant. Proc. 36, 2949 (2004), DOI: 10.1016/j.transproceed.2004.12.013. Crossref, Google Scholar
K. Parket al., Transplant. Proc. 31, 356 (1999), DOI: 10.1016/S0041-1345(98)01659-5. Crossref, Google Scholar
A. E. Roth, T. Sönmez and M. U. Ünver, Q. J. Econ. 119, 457 (2004). Crossref, Google Scholar
A. E. Roth, T. Sönmez and M. U. Ünver, A kidney exchange clearinghouse in New England, Am. Econ. Rev. Papers Proc. 95 (2005) 376–380 . Google Scholar
A. E. Roth, T. Sönmez and M. U. Ünver, J. Econ. Theor. 125, 151 (2005), DOI: 10.1016/j.jet.2005.04.004. Crossref, Google Scholar
A. E. Roth, T. Sönmez and M. U. Ünver, Am. Econ. Rev. 97, 828 (2007). Crossref, Google Scholar
S. L. Saidmanet al., Transplantation 81(5), 773 (2006), DOI: 10.1097/01.tp.0000195775.77081.25. Crossref, Google Scholar
S. L. Saidmanet al., Am. J. Transplant. 6, 2694 (2006). Google Scholar
S. L. Segevet al., J. Am. Med. Assoc. 293, 1883 (2005), DOI: 10.1001/jama.293.15.1883. Crossref, Google Scholar
United Network for Organ Sharing website, http://www.unos.org . Google Scholar