Stable Marriage Stable Pair (SMSP)
Category: Matching
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, and a designated couple Alice and Bob.
Problem
Are Alice and Bob a stable pair for the given instance of the problem?
Definitions
Alice and Bob are a stable pair if they are married to each other in some stable marriage.
Status
Open (Mayr and Subramanian [1], Subramanian [2]).
Remarks
This problem is in $\CC$, that is, it is equivalent to CCVP.
References
- E. W. Mayr and A. Subramanian (1992). The complexity of circuit value and network stability.
- A. Subramanian (1989). A new approach to stable matching problems.
- Greenlaw, R., Hoover, H. J., and Ruzzo, W. L. (1995). Limits to Parallel Computation: P-Completeness Theory. Oxford University Press. Problem B.8.5.