The Complexity of Counting Stable Marriages 论文

摘要

In an instance of size n of the stable marriage problem, each of n men and n women ranks the members of the opposite sex in order of preference. A 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. It is well known that at least one stable matching exists for every stable marriage instance, so that the decision version of the problem always has a “yes” answer. Furthermore, efficient algorithms are known for the determination of such a stable matching, so that the search version of the problem is polynomially solvable. However, by exploring the structure of the set of stable matchings for any particular instance of the problem, and exploiting its relationship with the set of antichains of an associated partially ordered set, we prove that the enumeration version of the problem—determining the number of stable matchings—is # P-complete, and therefore cannot be solved in polynomial time if ${\bf P} \ne {\bf NP}$.