The Complexity of Approximately Counting Stable Roommate Assignments

Details The Complexity of Approximately Counting Stable Roommate Assignments The Complexity of Approximately Counting Stable Roommate Assignments

2010-12-06

arxiv.org/abs/1012.1237v2

JCSS 2012

Computer Science

Computational Complexity

Scientific paper

10.1016/j.jcss.2012.02.003

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. We show that counting the number of stable roommate assignments in the $k$-attribute model ($k \geq 4$) and the 3-Euclidean model($k \geq 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 the authors, 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\Pi_1$. Hence, our result shows that an FPRAS for counting stable roommate assignments in the 3-attribute model would give an FPRAS for all of $#RH\Pi_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.

Affiliated with

Also associated with

No associations

Rating

The Complexity of Approximately Counting Stable Roommate Assignments does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The Complexity of Approximately Counting Stable Roommate Assignments, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Complexity of Approximately Counting Stable Roommate Assignments will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-168265