## 4 Changing \(k\) Men's Preference Lists
### Optimization Variant  
From the discussion in Section 3.1, it seems that it would suffice to choose \(k\) men whose preference lists are to be modified, and move their man-optimal partners to the top of their respective preference lists. If this is true, we obtain an \(O(n^{k+2})\)-time algorithm since there are \(O(n^{k})\) combinations of selecting \(k\) men and for each of them, we run GS whose time complexity is \(O(n^{2})\). However, the following example (Figure 3) shows that this is not true. Nevertheless, the following lemma allows the search space to be bounded. **Lemma 4.2**: _For an instance \(I\), let \(I_{opt}\) be an optimal solution and \(M_{opt}\) be the man-optimal stable matching of \(I_{opt}\). Let \(S\) (\(|S|\leq k\)) be the set of men whose preference lists are modified in \(I_{opt}\). Let \(\tilde{I}\) be the instance obtained from \(I\) by moving \(M_{opt}(m)\) to the top of \(m\)'s list for each \(m\in S\). Then \(M_{opt}\) is stable, and in fact man-optimal stable, for \(\tilde{I}\)._  
_Proof._ Suppose that \(M_{opt}\) has a blocking pair in \(\tilde{I}\). Each \(m\in S\) cannot be a part of a blocking pair because \(M_{opt}(m)\) lies at the top of \(m\)'s list. But men not in \(S\) and all the women have the same preference list in \(I_{opt}\) and \(\tilde{I}\), so if \((m^{\prime},w^{\prime})\) is a blocking pair for \(M_{opt}\) in \(\tilde{I}\), then \((m^{\prime},w^{\prime})\) is also a blocking pair for \(M_{opt}\) in \(I_{opt}\), a contradiction. Hence \(M_{opt}\) is stable for \(\tilde{I}\). Now suppose that \(M_{opt}\) is not man-optimal for \(\tilde{I}\) and let \(M^{\prime}(\
eq M_{opt})\) be the man-optimal stable matching for \(\tilde{I}\). Since \(M_{opt}\) matches every man in \(S\) to his top choice in \(\tilde{I}\), so does \(M^{\prime}\). Thus some of the men not in \(S\) (whose preference lists are the same in \(I\) and \(\tilde{I}\)) obtain better partners in \(M^{\prime}\) than in \(M_{opt}\). This means that \(MO_{I}(\tilde{I})<MO_{I}(I_{opt})\), which contradicts the optimality of \(I_{opt}\). By the definition of the problem, each man is matched in \(M_{opt}\) to the woman \(M_{0}(m)\) or a woman preceding \(M_{0}(m)\). Hence by Lemma 4.2, if we fix the set of \(\ell\) men whose preference lists are to be modified, it suffices to bring, for each selected man \(m\), \(M_{0}(m)\) or a woman preceding \(M_{0}(m)\) to the top. Furthermore, we know that there is no stable matching for \(I_{opt}\) in which _every_ man in \(S\) is matched to a woman strictly better than his man-optimal partner in \(M_{0}\)[2]. Hence for at least one man \(m^{*}\) in \(S\), \(M_{opt}(m^{*})=M_{0}(m^{*})\). Putting these observations together, we have the following Algorithm 3. Let \(X\) be the set of men in a given instance. ```
1:\(m_{1}\), \(m_{2}\), \(m_{3}\), \(m_{4}\), \(m_{



### Decision Variant

A straightforward extension of Sections 3.2 and 4.2 is as follows. We first find the man-optimal stable matching \(M_{0}\) and construct the reduced list \(RL_{I,M_{0}}\) and the rotation digraph \(D_{I,M_{0}}\) using \(O(n^{2})\) time. For each of the \(O(n^{2k-1})\) possible modifications of preference lists, we modify \(D_{I,M_{0}}\) in time \(O(kn)\) and check if the resulting graph contains a directed cycle in time \(O(n)\). If at least one execution creates a directed cycle, then the answer is \"yes\", otherwise \"no\". This results in the time complexity of \(O(n^{2}+n^{2k-1}(kn+n))=O(kn^{2k})\). We can reduce the search space significantly using the following idea. Suppose that input \(I\) is a \"yes\"-instance of PMI(\(k\)), and let \(I_{opt}\) be its optimal solution (when \(I\) is viewed as an MMI(\(k\)) instance). Let \(S\) (\(|S|\leq k\)) be the set of men whose preference lists are modified in \(I_{opt}\).