Finding a 2-way stable 3-way exchange
Can we decide in polynomial time if a directed preference system has a 2-way stable 3-way exchange?
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  and .
- Zs. Karkus, The 2-way stable 3-way exchange problem is NP-complete, EGRES Quick-Proof no. 2014-02
- 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