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 first polynomial time algorithm for the stable roommates problem was by Irving @cite_11 in 1985. A characterization of roommates instances that admit stable matchings was given in @cite_18 and new polynomial time algorithms for the stable roommates problem were given in @cite_0 @cite_14 . As mentioned earlier, G "ardenfors @cite_3 introduced the notion of popularity in the stable matching problem in bipartite instances.
@cite_18 @cite_14 @cite_3 @cite_0 @cite_11
2117557063 2029388009 2138100238 1623719451
We introduce a restriction of the stable roommates problem in which roommate pairs are ranked globally. In contrast to the unrestricted problem, weakly stable matchings are guaranteed to exist, and additionally, they can be found in polynomial time. However, it is still the case that strongly stable matchings may not exist, and so we consider the complexity of finding weakly stable matchings with various desirable properties. In particular, we present a polynomial-time algorithm to find a rank-maximal (weakly stable) matching. This is the first generalization of an algorithm due to [ 06] to a nonbipartite setting. Also, we describe several hardness results in an even more restricted setting for each of the problems of finding weakly stable matchings that are of maximum size, are egalitarian, have minimum regret, and admit the minimum number of weakly blocking pairs. 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. In a recent paper, Weems introduced the bistable matching problem, and asked if a polynomial-time algorithm exists to decide the feasibility of the bistable roommates problem. We resolve this question in the affirmative using linear programming. In addition, we show that several (old and new) results for the bistable marriage and roommates problem become transparent using the polyhedral approach. This technique has been used recently by the authors to address classical stable matching problems. We investigate the complexity of approximately counting stable roommate assignments in two models: (i) the k-attribute model, in which the preference lists are determined by dot products of ''preference vectors'' with ''attribute vectors'' and (ii) the k-Euclidean model, in which the preference lists are determined by the closeness of the ''positions'' of the people to their ''preferred positions''. Exactly counting the number of assignments is #P-complete, since Irving and Leather demonstrated #P-completeness for the special case of the stable marriage problem (Irving and Leather, 1986 [11]). We show that counting the number of stable roommate assignments in the k-attribute model (#k-attribute SR, k>=4) and the 3-Euclidean model (#k-Euclidean SR, k>=3) is interreducible, in an approximation-preserving sense, with counting independent sets (of all sizes) (#IS) in a graph, or counting the number of satisfying assignments of a Boolean formula (#SAT). This means that there can be no FPRAS for any of these problems unless NP=RP. As a consequence, we infer that there is no FPRAS for counting stable roommate assignments (#SR) unless NP=RP. Utilizing previous results by Chebolu, Goldberg and Martin (2010) [3], we give an approximation-preserving reduction from counting the number of independent sets in a bipartite graph (#BIS) to counting the number of stable roommate assignments both in the 3-attribute model and in the 2-Euclidean model. #BIS is complete with respect to approximation-preserving reductions in the logically-defined complexity class #RH@P"1. Hence, our result shows that an FPRAS for counting stable roommate assignments in the 3-attribute model would give an FPRAS for all #RH@P"1. We also show that the 1-attribute stable roommate problem always has either one or two stable roommate assignments, so the number of assignments can be determined exactly in polynomial time.