Three-Dimensional Stabl Matching Problems

The stable marriage problem is a matching problem that pairs members of two sets. The objective is to achieve a matching that satisfies all participants based on their preferences. The stable roommate problem is a variant involving only one set, which is partitioned into pairs with a similar objective. There exist asymptotically optimal algorithms that solve both problems. In this paper, the complexity of three-dimensional extensions of these problems is investigated. This is one of twelve research directions suggested by Knuth in his book on the stable marriage problem. It is shown that these problems are NP-complete, and hence it is unlikely that there exist efficient algorithms for their solutions. The approach developed in this paper provides an alternate NP-completeness proof for the hospitals/residents problem with couples—an important practical problem shown earlier to be NP-complete by Ronn.