We consider the popular matching problem in a roommates instance with strict preference lists. While popular matchings always exist in a bipartite instance, they need not exist in a roommates instance. The complexity of the popular matching problem in a roommates instance has been an open problem for several years and here we show it is NP-hard. A sub-class of max-size popular matchings called dominant matchings has been well-studied in bipartite graphs. We show that the dominant matching problem in a roommates instance is also NP-hard and this is the case even when the instance admits a stable matching.
The stable roommates problem is a well-known problem of matching n people into n2 disjoint pairs so that no two unmatched persons both prefer each other to their partners under the matching. We call such a matching “a complete stable matching.” It is known that a complete stable matching may not exist. Irving described an O(n2) algorithm that would find one complete stable matching if there is one, or would report that none exists. In this paper, we give a necessary and sufficient condition for the existence of a complete stable matching; namely, the non-existence of any odd party, which will be defined subsequently. We define a new structure called a “stable partition,” which generalizes the notion of a complete stable matching, and prove that every instance of the stable roommates problem has at least one such structure. We also show that a stable partition contains all the odd parties, if there are any. Finally we have an O(n2) algorithm that finds one stable partition which in turn gives all the odd parties. We study the classical stable marriage and stable roommates problems using a polyhedral approach. We propose a new LP formulation for the stable roommates problem, which has a feasible solution if and only if the underlying roommates problem has a stable matching. Furthermore, for certain special weight functions on the edges, we construct a 2-approximation algorithm for the optimal stable roommates problem. Our technique exploits features of the geometry of fractional solutions of this formulation. For the stable marriage problem, we show that a related geometry allows us to express any fractional solution in the stable marriage polytope as a convex combination of stable marriage solutions. This also leads to a genuinely simple proof of the integrality of the stable marriage polytope. The stable marriage problem, i.e., the problem of assigning the members of two disjoint sets to one another is extended to the case in which individual preferences are represented by weak orderings instead of linear orderings. This leads to a more natural solution for such problems as the processing of college admissions and the optimal distribution of personnel. The paper begins with a formal definition of an assignments function and introduces conditions on it, among them stability. It is shown how the Gale and Shapley algorithm for finding stable assignments can be extended to the more general case considered here. It is shown that if there is an assignment which is preferred by a majority to all other assignments, then this assignment is necessarily stable. Moreover, in a situation where all preference orders are linear orders, all stable assignments are majority assignments. It is shown that Stable Matching problems are the same as problems about stable configurations of X-networks. Consequences include easy proofs of old theorems, a new simple algorithm for finding a stable matching, an understanding of the difference between Stable Marriage and Stable Roommates, NP-completeness of Three-party Stable Marriage, CC-completeness of several Stable Matching problems, and a fast parallel reduction from the Stable Marriage problem to the Assignment problem. 