The complexity of approximately counting stable roommate assignments

详细信息	查看全文 | 推荐本文 |

• 作者：Prasad Chebolu¹ ; Leslie Ann Goldberg² ; Russell Martin ; ¹ ; ^{Russell.Martin@liverpool.ac.uk}
• 关键词：Approximate counting ; Roommate assignment problem
• 刊名：Journal of Computer and System Sciences
• 出版年：2012
• 期刊代码：186_00220000
• 类别：et
• 出版时间：September, 2012
• 卷：78
• 期：5
• 页码：1579-1605
• 文件大小：358 K

摘要

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 鈥減reference vectors鈥?with 鈥渁ttribute vectors鈥?and (ii) the k-Euclidean model, in which the preference lists are determined by the closeness of the 鈥減ositions鈥?of the people to their 鈥減referred 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 ). We show that counting the number of stable roommate assignments in the k-attribute model (#k-attribute SR, ) and the 3-Euclidean model (#k-Euclidean SR, ) is interreducible, in an approximation-preserving sense, with counting independent sets (of all sizes) () in a graph, or counting the number of satisfying assignments of a Boolean formula (). 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 () unless NP = RP. Utilizing previous results by Chebolu, Goldberg and Martin (2010) , we give an approximation-preserving reduction from counting the number of independent sets in a bipartite graph () to counting the number of stable roommate assignments both in the 3-attribute model and in the 2-Euclidean model. is complete with respect to approximation-preserving reductions in the logically-defined complexity class . Hence, our result shows that an FPRAS for counting stable roommate assignments in the 3-attribute model would give an FPRAS for all . 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.