|
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 egres.elte.hu}}, |
| INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
| YEAR | = | {2009}, |
| NUMBER | = | {TR-2009-01} |