<XML><RECORDS><RECORD><REFERENCE_TYPE>10</REFERENCE_TYPE><REFNUM>8285</REFNUM><AUTHORS><AUTHOR>Irving,R.W.</AUTHOR></AUTHORS><YEAR>2006</YEAR><TITLE>The cycle roommates problem: a hard case of kidney exchange</TITLE><PLACE_PUBLISHED>DCS Technical Report Series</PLACE_PUBLISHED><PUBLISHER>Dept of Computing Science, University of Glasgow</PUBLISHER><ISBN>TR-2006-225</ISBN><LABEL>Irving:2006:8285</LABEL><KEYWORDS><KEYWORD>Matching; stability; NP-complete problems</KEYWORD></KEYWORDS<ABSTRACT>Recently, a number of interesting algorithmic problems have arisen from the emergence, in a number of countries, of kidney exchange schemes, whereby live donors are matched with recipients according to compatibility and other considerations. One such problem can be modeled by a variant of the well-known stable roommates problem in which blocking cycles, as well as the normal blocking pairs, are significant. We show here that this variant of the stable roommates problem is NP-complete, thus solving an open question posed by Cechlarova and Lacko.</ABSTRACT></RECORD></RECORDS></XML>