The stable marriage problem with restricted pairs

AbstractA stable matching is a complete matching of men and women such that no man and woman who are not partners both prefer each other to their actual partners under the matching. In an instance of the STABLE MARRIAGE problem, each of the n men and n women ranks the members of the opposite sex in order of preference. It is well known that at least one stable matching exists for every STABLE MARRIAGE problem instance. We consider extensions of the STABLE MARRIAGE problem obtained by forcing and by forbidding sets of pairs. We present a characterization for the existence of a solution for the STABLE MARRIAGE WITH FORCED AND FORBIDDEN PAIRS problem. In addition, we describe a reduction of the STABLE MARRIAGE WITH FORCED AND FORBIDDEN PAIRS problem to the STABLE MARRIAGE WITH FORBIDDEN PAIRS problem. Finally, we also present algorithms for finding a stable matching, all stable pairs and all stable matchings for this extension. The complexities of the proposed algorithms are the same as the best known algorithms for the unrestricted version of the problem