Stable Marriage (SM)
Input
A set of $n$ men and a set of $n$ women. For each person a ranking of the opposite sex according to their preference for a marriage partner. Note that a preference list does not need to include a ranking for every member of the opposite sex. This problem is sometimes called the Stable Roommates Problem.
Problem
Does the given instance of the problem have a set of marriages that is stable? The set is stable (or a set of stable marriages) if there is no unmatched pair $\{m, w\}$ such that both $m$ and $w$ prefer each other to their current partners.
Status
Open (Mayr and Subramanian [1], Pólya, Tarjan, and Woods [2]).
Remarks
This problem is in $\CC$, that is, it is equivalent to CCVP.
See, for example, Gibbons [3] or [2] for background on SM. If the preference lists are complete, the problem always has a solution [2]. Several variations of SM are also known to be in $\CC$. For example, the male-optimal Stable Marriage Problem in which there is a designated couple $\{m, w\}$ and the question asked is whether man $m$ is married to woman $w$ in the male-optimal stable marriage? [1]. The male-optimal stable marriage is the one formed by the algorithm given in [2]. It finds a matching in which no man could do any better in a stable marriage. Several other versions of SM are discussed in SMFP, SMSP and SMMR.
References
- E. W. Mayr and A. Subramanian (1992). The complexity of circuit value and network stability.
- G. Pólya, R. E. Tarjan, and D. R. Woods (1983). Notes on Introductory Combinatorics.
- A. M. Gibbons (1985). Algorithmic Graph Theory.
- Greenlaw, R., Hoover, H. J., and Ruzzo, W. L. (1995). Limits to Parallel Computation: P-Completeness Theory. Oxford University Press. Problem B.8.3.