  In the Stable Roommates problem, we seek a stable matching of the agents into
pairs, in which no two agents have an incentive to deviate from their
assignment. It is well known that a stable matching is unlikely to exist, but a
stable partition always does and provides a succinct certificate for the
unsolvability of an instance. Furthermore, apart from being a useful structural
tool to study the problem, every stable partition corresponds to a stable
half-matching, which has applications, for example, in sports scheduling and
time-sharing.
  We establish new structural results for stable partitions and show how to
enumerate all stable partitions and the cycles included in such structures
efficiently. We also adapt optimality criteria from stable matchings to stable
partitions and give complexity and approximability results for the problems of
computing such "fair" and "optimal" stable partitions.
  Through this research, we contribute to a deeper understanding of stable
partitions from a combinatorial point of view, as well as the computational
complexity of computing "fair" or "optimal" stable half-matchings in practice,
closing the gap between integral and fractional stable matchings and paving the
way for further applications of stable partitions to unsolvable instances and
computationally hard stable matching problems.
