3人部屋安定ルームメイト問題のNP完全性

Abstract

安定ルームメイト問題は, 希望リストに基づいて「安定性」を満たすように, 2N人の人間をN組のペアに分割する問題である.安定ルームメイト問題は解を持たない場合もあるが, 解を持つか否かを判定し, 持つ場合には解を見つける多項式時間アルゴリズムが知られている.本研究ではこの問題を拡張し, 3N人の人間をN組のトリプルに分割する問題を提案する.そして, この問題において解の存在を判定する問題がNP完全であることを示す.

In the stable roommates problem, we are given 2N people, each having a preference list that ranks remaining 2N-1 people in a strict order according to his/her preferences. It asks to find a stable matching, namely, a set of N pairs that satisfies the "stability" condition. There are instances that have no solution, but Irving has developed a polynomial time algorithm that decides if there exists a solution, and finds one if exists. We extend this problem into 3-dimension. In our problem, we are given 3N people and are asked to partition them into N triples. We prove that the problem of deciding if a stable matching exists is NP-complete.