TR-2009-01

Stable roommates with free edges

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



Abstract

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:

@techreport{egres-09-01,
AUTHOR = {Cechl{\'a}rov{\'a}, Katar{\'i}na and Fleiner, Tam{\'a}s},
TITLE = {Stable roommates with free edges},
NOTE= {{\tt www.cs.elte.hu/egres}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2009},
NUMBER = {TR-2009-01}
}


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