The complexity of approximately counting stable roommate assignments

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⩾4k⩾4) and the 3-Euclidean model (#k-Euclidean SR, k⩾3k⩾3) is interreducible, in an approximation-preserving sense, with counting independent sets (of all sizes) (#IS#IS) in a graph, or counting the number of satisfying assignments of a Boolean formula (#SAT#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#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#BIS) to counting the number of stable roommate assignments both in the 3-attribute model and in the 2-Euclidean model. #BIS#BIS is complete with respect to approximation-preserving reductions in the logically-defined complexity class #RHΠ1#RHΠ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Π1#RHΠ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.

► #4-attribute stable roommate assignments is AP-equivalent to #IS#IS in a graph.
► The 1-attribute stable roommate problem is polynomially-time solvable.
► #3-Euclidean stable roommate assignments is AP-equivalent to #IS#IS in a graph.
► We give AP-reductions from #BIS#BIS to #3-attribute SR and 2-Euclidean SR.