Jiehua Chen

Paper accepted at ICALP 2018: How hard is it to satisfy (almost) all roommates?

Posted on by Jiehua Chen


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.