# Finding a 2-way stable 3-way exchange

From Egres Open

Can we decide in polynomial time if a directed preference system has a 2-way stable 3-way exchange?

It was proved by Zsuzsa Karkus ^{[1]}^{[2]} that the problem is NP-complete. Moreover, it is proved in ^{[2]} that the problem is W[1]-hard if the parameter is the number of triangles in the exchange.

## Remarks

The problem of deciding if a 3-way stable 3-way exchange exists is NP-complete, because the Cyclic Stable Matching problem with incomplete lists is a special case. The 2-way stable 2-way exchange problem is equivalent to the stable roommates problem, which can be solved in polynomial time. Some related results are presented in ^{[3]} and ^{[4]}.

## References

- ↑ Zs. Karkus,
*The 2-way stable 3-way exchange problem is NP-complete*, EGRES Quick-Proof no. 2014-02 - ↑
^{2.0}^{2.1}Zs. Karkus,*Hardness results for stable exchange problems*, EGRES Technical Report no. 2015-15 - ↑ P. Biró,
*Stable exchange of indivisible goods with restrictions*, author link. - ↑ P. Biró, E. McDermid,
*Three-Sided Stable Matchings with Cyclic Preferences*, DOI link, conference version