Adapting Stable Matchings to Forced and Forbidden Pairs
share
We introduce the problem of adapting a stable matching to forced and forbidden pairs. Specifically, given a stable matching M_1, a set Q of forced pairs, and a set P of forbidden pairs, we want to find a stable matching that includes all pairs from Q, no pair from P, and that is as close as possible to M_1. We study this problem in four classical stable matching settings: Stable Roommates (with Ties) and Stable Marriage (with Ties). As our main contribution, we develop an algorithmic technique to "propagate" changes through a stable matching. This technique is at the core of our polynomial-time algorithm for adapting Stable Roommates matchings to forced pairs. In contrast to this, we show that the same problem for forbidden pairs is NP-hard. However, our propagation technique allows for a fixed-parameter tractable algorithm with respect to the number of forbidden pairs when both forced and forbidden pairs are present. Moreover, we establish strong intractability results when preferences contain ties.
READ FULL TEXT