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.

翻译：我们引入了稳定匹配强制和禁止配对的问题。 具体地说, 在稳定匹配$1美元、 一套固定的强制配对美元和一套固定的禁止配对美元的情况下, 我们想要找到一种稳定的匹配, 包括从美元到美元的所有配对, 而不是从美元到美元, 并且尽可能接近1美元。 我们用四个典型的稳定匹配环境来研究这个问题: 稳定的室友( 带领) 和稳定的婚姻( 带领) 。 作为我们的主要贡献, 我们开发了一种算法技术, 通过稳定匹配来改变“ 配对 ” 。 这个技术是我们将稳定的室友配对与强制配对的多元- 时间算法的核心。 与此相反, 我们显示, 禁止配对的问题同样是硬的。 但是, 我们的传播技术允许在强制和禁止配对都存在的时候, 使用固定的 与禁配对数量 的可调控的算法 。 此外, 当偏重时, 我们确定了强烈的耐性结果 。