Hardness results on the man-exchange stable marriage problem with short preference lists

Eric Mc Dermid, Christine Cheng, and Ichiro Suzuki
Information Processing Letters
Volume 101, Issue 1, 16 January 2007, Pages 13-19
http://dx.doi.org/10.1016/j.ipl.2006.07.005

安定結婚問題に関する論文。
Irvingは最近「man-exchange stable matching」という概念を提出したようで、それにはman-exchange blocking pairとい概念を定義すればよい。
マッチングにおけるman-exchange blocking pairとは男性のペアでその2人のパートナーを入れ替えた方が両方ともうれしくなるもののこと。
このとき、man-exchange blocking pairを持たない安定マッチングをman-exchange stable matchingと呼ぶ。
問題はman-exchange stable matchingの存在性である。
Irvingはこの問題がNP完全であることを証明し、さらに男女の選好リストに3人までしか名前を書けない場合には多項式時間アルゴリズムを設計した。
この論文ではリストに書ける人数が4以上の任意の定数である場合には問題がNP完全になることを示している。の