{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,17]],"date-time":"2026-01-17T18:56:30Z","timestamp":1768676190268,"version":"3.49.0"},"reference-count":47,"publisher":"MDPI AG","issue":"2","license":[{"start":{"date-parts":[[2019,2,25]],"date-time":"2019-02-25T00:00:00Z","timestamp":1551052800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>In order to increase the potential kidney transplants between patients and their incompatible donors, kidney exchange programs have been created in many countries. In the programs, designing algorithms for the kidney exchange problem plays a critical role. The graph theory model of the kidney exchange problem is to find a maximum weight packing of vertex-disjoint cycles and chains for a given weighted digraph. In general, the length of cycles is not more than a given constant L (typically     2 \u2264 L \u2264 5), and the objective function corresponds to maximizing the number of possible kidney transplants. In this paper, we study the parameterized complexity and randomized algorithms for the kidney exchange problem without chains from theory. We construct two different parameterized models of the kidney exchange problem for two cases     L = 3     and     L \u2265 3, and propose two randomized parameterized algorithms based on the random partitioning technique and the randomized algebraic technique, respectively.<\/jats:p>","DOI":"10.3390\/a12020050","type":"journal-article","created":{"date-parts":[[2019,2,25]],"date-time":"2019-02-25T10:56:53Z","timestamp":1551092213000},"page":"50","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Randomized Parameterized Algorithms for the Kidney Exchange Problem"],"prefix":"10.3390","volume":"12","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4938-4407","authenticated-orcid":false,"given":"Mugang","family":"Lin","sequence":"first","affiliation":[{"name":"School of Computer Science and Engineering, Central South University, Changsha 410083, China"},{"name":"School of Computer Science and Technology, Hengyang Normal University, Hengyang 421002, China"},{"name":"Hunan Provincial Key Laboratory of Intelligent Information Processing and Application, Hengyang 421002, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jianxin","family":"Wang","sequence":"additional","affiliation":[{"name":"School of Computer Science and Engineering, Central South University, Changsha 410083, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Qilong","family":"Feng","sequence":"additional","affiliation":[{"name":"School of Computer Science and Engineering, Central South University, Changsha 410083, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bin","family":"Fu","sequence":"additional","affiliation":[{"name":"Department of Computer Science, The University of Texas Rio Grande Valley, Edinburg, TX 78539, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2019,2,25]]},"reference":[{"key":"ref_1","first-page":"5","article-title":"The case for a living emotionally related international kidney donor exchange registry","volume":"18","author":"Rapaport","year":"1986","journal-title":"Transpl. Proc."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1016\/j.ejor.2013.05.025","article-title":"New insights on integer-programming models for the kidney exchange problem","volume":"231","author":"Constantino","year":"2013","journal-title":"Eur. J. Oper. Res."},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Abraham, D.J., Blum, A., and Sandholm, T. (2007, January 11\u201315). Clearing algorithms for barter exchange markets: enabling nationwide kidney exchanges. Proceedings of the 8th ACM Conference on Electronic Commerce, San Diego, CA, USA.","DOI":"10.1145\/1250910.1250954"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"499","DOI":"10.1142\/S1793830909000373","article-title":"Maximum weight cycle packing in directed graphs, with application to kidney exchange programs","volume":"1","author":"Manlove","year":"2009","journal-title":"Discrete Math. Algorithms Appl."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"828","DOI":"10.1257\/aer.97.3.828","article-title":"Efficient kidney exchange: Coincidence of wants in markets with compatibility-based preferences","volume":"97","author":"Roth","year":"2007","journal-title":"Am. Econ. Rev."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"457","DOI":"10.1162\/0033553041382157","article-title":"Kidney exchange","volume":"119","author":"Roth","year":"2004","journal-title":"Q. J. Econ."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"1883","DOI":"10.1001\/jama.293.15.1883","article-title":"Kidney paired donation and optimizing the use of live donor organs","volume":"293","author":"Segev","year":"2005","journal-title":"JAMA"},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Xiao, M., and Wang, X. (2018, January 13\u201319). Exact algorithms and complexity of kidney exchange. Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, Stockholm, Sweden.","DOI":"10.24963\/ijcai.2018\/77"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"984","DOI":"10.1111\/j.1600-6143.2011.03481.x","article-title":"Nonsimultaneous chains and dominos in kidney-paired donation\u2013Revisited","volume":"11","author":"Ashlagi","year":"2011","journal-title":"Am. J. Transpl."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"498","DOI":"10.1287\/msom.2014.0496","article-title":"Kidney exchange with long chains: an efficient pricing algorithm for clearing barter exchanges with branch-and-price","volume":"16","author":"Glorie","year":"2014","journal-title":"Manuf. Serv. Oper. Manag."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"663","DOI":"10.1073\/pnas.1421853112","article-title":"Finding long chains in kidney exchange using the traveling salesman problem","volume":"112","author":"Anderson","year":"2015","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"6:1","DOI":"10.1145\/2670129","article-title":"Paired and altruistic kidney donation in the UK: algorithms and experimentation","volume":"19","author":"Manlove","year":"2015","journal-title":"J. Exp. Algorithmics"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"144","DOI":"10.1053\/j.ajkd.2010.10.005","article-title":"Kidney paired donation: Fundamentals, limitations, and expansions","volume":"57","author":"Gentry","year":"2011","journal-title":"Am. J. Kidney Dis."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1007\/s00453-009-9356-6","article-title":"Circular stable matching and 3-way kidney transplant","volume":"58","author":"Huang","year":"2010","journal-title":"Algorithmica"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"316","DOI":"10.1287\/opre.46.3.316","article-title":"Branch-and-price: column generation for solving huge integer programs","volume":"46","author":"Barnhart","year":"1998","journal-title":"Oper. Res."},{"key":"ref_16","unstructured":"Klimentova, X., Alvelos, F., and Viana, A. (July, January 30). A new branch-and-price approach for the kidney exchange problem. Proceedings of the 14th International Conference on Computational Science and Its Applications, Guimar\u00e3es, Portugal."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1287\/opre.8.1.101","article-title":"Decomposition principle for linear programs","volume":"8","author":"Dantzig","year":"1960","journal-title":"Oper. Res."},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Dickerson, J.P., Manlove, D.F., Plaut, B., Sandholm, T., and Trimble, J. (2016, January 24\u201328). Position-indexed formulations for kidney exchange. Proceedings of the 2016 ACM Conference on Economics and Computation, Maastricht, The Netherlands.","DOI":"10.1145\/2940716.2940759"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1016\/j.cor.2018.06.008","article-title":"A polyhedral study of the cardinality constrained multi-cycle and multi-chain problem on directed graphs","volume":"99","year":"2018","journal-title":"Comput. Oper. Res."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1007\/s10878-015-9932-4","article-title":"On the kidney exchange problem: Cardinality constrained cycle and chain problems on directed graphs: A survey of integer programming approaches","volume":"33","year":"2017","journal-title":"J. Comb. Optim."},{"key":"ref_21","unstructured":"Luo, S., Tang, P., Wu, C., and Zeng, J. (arXiv, 2018). Approximation of barter exchanges with cycle length constraints, arXiv."},{"key":"ref_22","unstructured":"Jia, Z., Tang, P., Wang, R., and Zhang, H. (2017, January 8\u201312). Efficient near-optimal algorithms for barter exchange. Proceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems, S\u00e3o Paulo, Brazil."},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Dickerson, J.P., Kazachkov, A.M., Procaccia, A.D., and Sandholm, T. (2017, January 4\u20139). Small representations of big kidney exchange graphs. Proceedings of the 31st AAAI Conference on Artificial Intelligence, San Francisco, CA, USA.","DOI":"10.1609\/aaai.v31i1.10593"},{"key":"ref_24","first-page":"6","article-title":"Iterative expansion and color coding: An improved algorithm for 3D-matching","volume":"8","author":"Chen","year":"2012","journal-title":"ACM T. Algorithms"},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1007\/s10878-013-9691-z","article-title":"Randomized parameterized algorithms for P2-Packing and Co-Path Packing problems","volume":"29","author":"Feng","year":"2015","journal-title":"J. Comb. Optim."},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Bj\u00f6rklund, A. (2010, January 23\u201326). Determinant sums for undirected hamiltonicity. Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science, Las Vegas, NV, USA.","DOI":"10.1109\/FOCS.2010.24"},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"Koutis, I. (2008, January 7\u201311). Faster algebraic algorithms for path and packing problems. Proceedings of the 35th International Colloquium on Automata, Languages and Programming, Reykjavik, Iceland.","DOI":"10.1007\/978-3-540-70575-8_47"},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Koutis, I., and Williams, R. (2009, January 5\u201312). Limits and applications of group algebras for parameterized problems. Proceedings of the 36th International Colloquium on Automata, Languages and Programming, Rhodos, Greece.","DOI":"10.1007\/978-3-642-02927-1_54"},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1016\/j.ipl.2008.11.004","article-title":"Finding paths of length k in O*(2k) time","volume":"109","author":"Williams","year":"2009","journal-title":"Inform. Process. Lett."},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Assadi, S., Khanna, S., and Li, Y. (2016, January 24\u201328). The stochastic matching problem with (very) few queries. Proceedings of the 2016 ACM Conference on Economics and Computation, Maastricht, Netherlands.","DOI":"10.1145\/2940716.2940769"},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"Chen, N., Immorlica, N., Karlin, A.R., Mahdian, M., and Rudra, A. (2009, January 5\u201312). Approximating matches made in heaven. Proceedings of 36th International Colloquium on Automata, Languages and Programming, Rhodes, Greece.","DOI":"10.1007\/978-3-642-02927-1_23"},{"key":"ref_32","unstructured":"Awasthi, P., and Sandholm, T. (2009, January 11\u201317). Online stochastic optimization in the large: Application to kidney exchange. Proceedings of the 21st International Joint Conference on Artificial Intelligence, Pasadena, CA, USA."},{"key":"ref_33","doi-asserted-by":"crossref","unstructured":"Fang, W., Filos-Ratsikas, A., Frederiksen, S.K.S., Tang, P., and Zuo, S. (2015, January 27\u201330). Randomized assignments for barter exchanges: Fairness vs. efficiency. In Proceedings of the 4th International Conference on Algorithmic Decision Theory, Lexington, KY, USA.","DOI":"10.1007\/978-3-319-23114-3_32"},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"1815","DOI":"10.1137\/140981290","article-title":"Deterministic algorithms for matching and packing problems based on representative sets","volume":"29","author":"Goyal","year":"2015","journal-title":"SIAM J. Discrete Math."},{"key":"ref_35","doi-asserted-by":"crossref","unstructured":"Downey, R.G., and Fellows, M.R. (1999). Parameterized Complexity, Springer.","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"ref_36","doi-asserted-by":"crossref","unstructured":"Cygan, M., Fomin, F.V., Kowalik, \u0141., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., and Saurabh, S. (2015). Parameterized Algorithms, Springer.","DOI":"10.1007\/978-3-319-21275-3"},{"key":"ref_37","unstructured":"Gabow, H.N. (1990, January 22\u201324). Data structures for weighted matching and nearest common ancestors with linking. Proceedings of the 1st Annual ACM-SIAM Symposium on Discrete Algorithms, San Francisco, CA, USA."},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"940","DOI":"10.1097\/00007890-201007272-01847","article-title":"The evolution of a successful kidney paired donation program","volume":"90","author":"Hanto","year":"2010","journal-title":"Transplantation"},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"125","DOI":"10.6028\/jres.069B.013","article-title":"Maximum matching and a polyhedron with 0, 1-vertices","volume":"69","author":"Edmonds","year":"1965","journal-title":"J. Res. Nat. Bur. Stand. Sec. B"},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1016\/j.jcss.2017.03.003","article-title":"Narrow sieves for parameterized paths and packings","volume":"87","author":"Husfeldt","year":"2017","journal-title":"J. Comput. Syst. Sci."},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"698","DOI":"10.1016\/j.jcss.2011.10.001","article-title":"Faster algorithms for finding and counting subgraphs","volume":"78","author":"Fomin","year":"2012","journal-title":"J. Comput. Syst. Sci."},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"146","DOI":"10.1137\/0201010","article-title":"Depth-First Search and Linear Graph Algorithms","volume":"1","author":"Tarjan","year":"1972","journal-title":"SIAM J. Comput."},{"key":"ref_43","unstructured":"Cechl\u00e1rov\u00e1, K., Fleiner, T., and Manlove, D.F. (2005, January 28\u201330). The kidney exchange game. Proceedings of the 8th International Symposium on Operational Research, Nova Gorica, Slovenia, Balkans."},{"key":"ref_44","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1016\/j.ipl.2006.09.012","article-title":"Inapproximability of the kidney exchange problem","volume":"101","year":"2007","journal-title":"Inform. Process. Lett."},{"key":"ref_45","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1007\/s00453-009-9315-2","article-title":"Three-sided stable matchings with cyclic preferences","volume":"58","author":"McDermid","year":"2010","journal-title":"Algorithmica"},{"key":"ref_46","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1007\/s10479-010-0691-4","article-title":"The kidney exchange problem: How hard is it to find a donor?","volume":"193","author":"Lacko","year":"2012","journal-title":"Ann. Oper. Res."},{"key":"ref_47","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1016\/j.tcs.2017.01.023","article-title":"Hardness results for stable exchange problems","volume":"670","year":"2017","journal-title":"Theor. Comput. Sci."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/12\/2\/50\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T12:34:35Z","timestamp":1760186075000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/12\/2\/50"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,2,25]]},"references-count":47,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2019,2]]}},"alternative-id":["a12020050"],"URL":"https:\/\/doi.org\/10.3390\/a12020050","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,2,25]]}}}