|
Published in:
In this paper we study variants of the stable exchange problem which can be viewed as a model for kidney exchange. The $b$-way stable $l$-way exchange problem is a generalization of the stable roommates problem. For $b=l=3$ Biró and McDermid proved that the problem is NP-complete and asked whether a polynomial time algorithm exists for $b=2, \ l=3$. We prove that the problem is NP-complete and it is W[1]-hard with the number of 3-cycles in the exchange as a parameter. We answer a question of Biró by proving that it is NP-hard to maximize the number of covered nodes in a stable exchange. We also prove some related results.
Bibtex entry:
| AUTHOR | = | {M{\'e}sz{\'a}ros-Karkus, Zsuzsa}, |
| TITLE | = | {Hardness results for stable exchange problems}, |
| NOTE | = | {{\tt egres.elte.hu}}, |
| INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
| YEAR | = | {2015}, |
| NUMBER | = | {TR-2015-15} |