The Complexity of Counting Stable Marriages
1986; Society for Industrial and Applied Mathematics; Volume: 15; Issue: 3 Linguagem: Inglês
10.1137/0215048
ISSN1095-7111
AutoresRobert W. Irving, P.S.H. Leather,
Tópico(s)Advanced Graph Theory Research
ResumoIn 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}$.
Referência(s)