Summary: We consider a generalization of the Stable Roommates problem (sr), in which preference lists may be partially ordered and forbidden pairs may be present, denoted by srpf. This includes, as a special case, a corresponding generalization of the classical Stable Marriage problem (sm), denoted by smpf. By extending previous work of Feder, we give a two-step reduction from srpf to 2-sat. This has many consequences, including fast algorithms for a range of problems associated with finding “optimal” stable matchings and listing all solutions, given variants of sr and sm. For example, given an smpf instance $I$, we show that there exists an $O(m)$ “succinct” certificate for the unsolvability of $I$, an $O(m)$ algorithm for finding all the super-stable pairs in $I$, an $O(m+kn)$ algorithm for listing all the super-stable matchings in $I$, an $O(m^{1.5})$ algorithm for finding an egalitarian super-stable matching in $I$, and an $O(m)$ algorithm for finding a minimum regret super-stable matching in $I$, where $n$ is the number of men, $m$ is the total length of the preference lists, and $k$ is the number of super-stable matchings in $I$. Analogous results apply in the case of srpf.