Finding a 2-way stable 3-way exchange

From Egres Open
Jump to: navigation, search

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

Solved b.jpg

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.


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].


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