Donald Bren School of Information and Computer Sciences

In an instance of the stable marriage problem of size n, n men and n women each ranks members of the opposite sex in order of preference. A stable marriage is a complete matching M = {(m_1, w_i_1), (m_2, w_i_2), ..., (m_n, w_i_n)} such that no unmatched man and woman prefer each other to their partners in M.

A pair (m_i, w_j) is stable if it is contained in some stable marriage. In this paper, we prove that determining if an arbitrary pair is stable requires Ω(n^2) time in the worst case. We show, by an adversary argument, that there exists instances of the stable marriage problem such that it is possible to find at least one pair that exhibits the Ω(n^2) lower bound.

As corollaries of our results, the lower bound of Ω(n^2) is established for several stable marriage related problems. Knuth, in his treatise on stable marriage, asks if there is an algorithm that finds a stable marriage in less than Θ(n^2) time. Our results show that such an algorithm does not exist.