Hardness results for stable exchange problems

Zsuzsa Mészáros-Karkus


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}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2015},
NUMBER = {TR-2015-15}

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