## 4 Changing \(k\) Men's Preference Lists
### Optimization Variant
From the discussion in Section 4.2, we can assume that in the preference list of one man \(m^{*}\), \(M_{0}(m^{*})\) is moved to the top in \(I_{opt}\), and in the preference list of other men \(m(\in S-\{m^{*}\})\), \(M_{0}(m)\) or a woman preceding \(M_{0}(m)\) is moved to the top. Clearly, the rotation digraph \(D_{I_{opt},M_{0}}\) must contain a directed cycle. Now, define \(S^{\prime}(\subseteq S)\) as \(S^{\prime}=\{m\mid M_{0}(m)\) is moved to the top of \(m\)'s list in \(I_{opt}\}\) and consider the instance \(\bar{I}\) constructed from \(I\) by moving \(M_{0}(m)\) to the top of \(m\)'s list for each \(m\in S^{\prime}\) (and leaving \(m\)'s preference list for each \(m\
otin S^{\prime}\) unchanged). By the construction of reduced lists and rotation digraphs, it is not hard to see that \(D_{\bar{I},M_{0}}\) is identical to \(D_{I_{opt},M_{0}}\) and hence \(D_{\bar{I},M_{0}}\) contains a directed cycle. (This can be seen as follows: If a man \(m\) is in \(S^{\prime}\) or not in \(S\), then \(m\)'s preference list is the same in \(I_{opt}\) and \(\bar{I}\). If a man \(m\) is in \(S-S^{\prime}\), then the _set_ of women preceding \(M_{0}(m)\) in \(m\)'s preference list is the same in \(I_{opt}\) and \(\bar{I}\).) Therefore, it suffices, for each combination of choosing \(i(\leq k)\) men, to move their man-optimal partners to the top of the lists, to modify the rotation digraph accordingly in \(O(in)\) time, and to check if the resulting digraph contains a directed cycle in \(O(n)\) time. The overall time complexity is

\[O(n^{2}+\sum_{i=1}^{k}(\binom{n}{i}(in+n))) = O(\sum_{i=1}^{k}\frac{n!}{(n-i)!i!}\cdot in)\]_Algorithms_**2013**, \(6\)

\[= O(\sum_{i=1}^{k}(\binom{n-1}{i-1}n^{2}))\] \[= O(n^{k+1}).\]

**Theorem 4.4**: _PMI(\(k\)) can be solved in \(O(n^{k+1})\) time._

## 5 Changing \(n\) Men's Preference Lists

In this section, we show that MMI(\(k\)) and PMI(\(k\)) become easy if we are allowed to change any number of men's preference lists. We first consider the optimization variant. Consider an instance \(I\) and its man-optimal stable matching \(M_{0}\). By the requirement of the problem, in a new matching each man \(m\) should be matched with the woman \(M_{0}(m)\) or a woman preceding \(M_{0}(m)\) in \(m\)'s list in \(I\); in other words, each man should be matched with a woman on the reduced lists \(RL_{I,M_{0}}\). Let \(M^{*}\) be a minimum score perfect matching with this property. If we move \(M^{*}(m)\) to the top of \(m\)'s list for each \(m\), we are done because \(M^{*}\) is clearly the man-optimal stable matching of the resulting instance. It is easy to find \(M^{*}\): We construct the edge-weighted bipartite graph \(G=(V,U,E)\) where \(V\) and \(U\) are the sets of men and women respectively, and \((m,w)\in E\) if and only if \(w\) appears on \(m\)'s reduced list in \(RL_{I,M_{0}}\). The weight of \((m,w)\) is the rank of \(w\) in \(m\)'s list in \(I\), that is, \(r_{m}(w)\). We can obtain \(M^{*}\) by finding a minimum cost perfect matching in \(G\), which can be done in \(O(n^{2.5}\log n)\) time [6, 7]. Since finding \(M_{0}\) and constructing \(RL_{I,M_{0}}\) can be done in \(O(n^{2})\) time, the overall time complexity is \(O(n^{2.5}\log n)\). **Theorem 5.1**: _MMI(\(n\)) can be solved in \(O(n^{2.5}\log n)\) time._

As for the decision variant, we do not need to find a minimum cost perfect matching but it suffices to check if \(M_{0}\) can be Pareto improved. We can do this by constructing the digraph \(G=(V,A)\), where each vertex of \(G\) corresponds to a woman in a given instance \(I\). For each man \(m\), we include an arc from \(M_{0}(m)\) to each woman preceding \(M_{0}(m)\) in \(m\)'s preference list. It is not hard to see that \(M_{0}\) can be Pareto improved if and only if \(G\) contains a directed cycle. As mentioned in the analysis of the time complexity of Algorithm 2 in Section 3.2, we can check whether \(G\) contains a directed cycle or not by a topological sorting algorithm in time linear in the size of \(G\).