Hardness results for stable exchange problems

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 on strong stability, approximation and variants of the problem where we allow chains.