TR-2015-15

Hardness results for stable exchange problems

Zsuzsa Mészáros-Karkus



Abstract

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:

@techreport{egres-15-15,
AUTHOR = {M{\'e}sz{\'a}ros-Karkus, Zsuzsa},
TITLE = {Hardness results for stable exchange problems},
NOTE= {{\tt www.cs.elte.hu/egres}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2015},
NUMBER = {TR-2015-15}
}


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