We studied the parameterized complexity of two optimization variants of the Stable Roommates problem: Egalitarian Stable Roommates and Minimum Blocking Pair Stable Roommates. In each problem, the parameter is the objective value, i.e. the sum γ of the ranks of the partners of each agent and the number β of blocking pairs in a solution. We showed that Egalitarian Stable Roommates can be solved in O^*(γ^O(γ)) time even if there are ties and the preferences could be incomplete while Minimum Blocking Pair Stable Roommates is W[1]-hard wrt. β even if there is no ties and each agent’s preference list has length at most five.
====================================
The paper is accepted and going to be presented at ICALP 2018 and an arxiv version can be found here.