Stable roommates with free edges

Katarína Cechlárová, Tamás Fleiner


In the well-known stable roommates problem we have given a graph with preferences on the stars and we are looking for a matching that is not blocked by a nonmatching edge. There are well-known algorithms to find such a matching or to conclude that no such matching exists. Here we consider a relaxed problem motivated by kidney exchanges, where not all edges of the graph can block a matching. We show that this problem is NP-complete and apply the result to give an alternative proof of an NP-completeness result of Ronn.

Bibtex entry:

AUTHOR = {Cechl{\'a}rov{\'a}, Katar{\'i}na and Fleiner, Tam{\'a}s},
TITLE = {Stable roommates with free edges},
NOTE= {{\tt}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2009},
NUMBER = {TR-2009-01}

Last modification: 22.11.2022. Please email your comments to Tamás Király!