Marriage and Roommate

Abstract

This paper has two objectives. One is to give a linear time algorithm that solves the stable roommates problem (i.e., obtains one stable matching) using the stable marriage problem. The idea is that a stable matching of a roommate instance $I$ is a stable matching (that however must satisfy a certain condition) of some marriage instance $I^{\prime }$. $I^{\prime }$ is obtained just by making two copies of $I$, one for the men's table and the other for the women's table. The second objective is to investigate the possibility of reducing the roommate problem to the marriage problem (with a one-to-one correspondence between their stable matchings) in polynomial time. For a given $I$, we construct the rotation POSET $P$ of $I^{\prime }$ and then we ``halve'' it to obtain $P^{\prime }$, by which we can forget the above condition and can use all the closed subsets of $P^{\prime }$ for all the stable matchings of $I$. Unfortunately, this approach works (runs in polynomial time) only for restricted instances.

accepted to IJFCS