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
