## 4 Changing \(k\) Men's Preference Lists  
### Hardness Result  
In this section, we show W[1]-hardness of MMI(\(k\)). This hardness implies that MMI(\(k\)) probably does not admit an FPT algorithm with parameter \(k\), _i.e._, an \(O(f(k)\cdot p(n))\)-time algorithm where \(f\) is any function and \(p\) is a polynomial. **Theorem 4.1**: _MMI(\(k\)) with parameter \(k\) is W[1]-hard._  
_Proof._ The Densest \(k\) Subgraph problem (D\(k\)S) [4] is the following problem. We are given a graph \(G\) and a positive integer \(k\). The task is to find an induced subgraph of \(G\) with \(k\) vertices that contains the maximum number of edges. It is known that D\(k\)S is W[1]-hard with parameter \(k\)[5]. We give an FPT-reduction from D\(k\)S to MMI(\(k\)). Given an instance \((G,k_{1})\) of D\(k\)S, we construct an instance \((I,k_{2})\) of MMI(\(k\)) as follows. First, we let \(k_{2}=k_{1}\). Next, we construct \(I\) from \(G=(V,E)\). For each vertex \(v_{i}\in V\), we construct a man \(m_{i}\) and a woman \(w_{i}\). For each edge \((v_{i},v_{j})\in E\), we construct two men \(m_{i,j}\) and \(m^{\prime}_{i,j}\) and two women \(w_{i,j}\) and \(w^{\prime}_{i,j}\). For a vertex \(v_{i}\in V\), let \(E_{i}\subseteq E\) be the set of edges incident to \(v_{i}\) and \(W_{i}\) be the set of women \(w_{i,j}\) corresponding to \(E_{i}\). Each person's preference list is constructed as follows, where \(L(W_{i})\) is an arbitrarily ordered list of women in \(W_{i}\) and \"\(\cdots\)\" means an arbitrarily ordered list of those people who do not appear explicitly in the list. \[ \begin{array}{llllll}m_{i}\makebox[0.0 pt][l]{:}&L(W_{i})\ w_{i}\cdots&\mbox {($1\leq i\leq|V|$)}&w_{i}\makebox[0.0 pt][l]{:}&m_{i}\cdots&\mbox{($1\leq i \leq|V|$)}\\ m_{i,j}\makebox[0.0 pt][l]{:}&w^{\prime}_{i,j}\ w_{i,j}\ \cdots&\mbox{($(i,j)\in E$)}&w_{i,j} \makebox[0.0 pt][l]{:}&m_{i,j}\ m_{i}\ m_{j}\ m^{\prime}_{i,j}\cdots&\mbox{($( i,j)\in E$)}\\ m^{\prime}_{i,j}\makebox[0.0 pt][l]{:}&w_{i,j}\ w^{\prime}_{i,j}\ \cdots&\mbox{($(i,j)\in E$)}&w^{\prime}_{i,j}\makebox[0.0 pt][l]{:}&m^{\prime}_ {i,j}\ m_{i,j}\cdots&\mbox{($(i,j)\in E$)}\\ \end{array} \]It is not hard to see that the man-optimal stable matching \(M_{0}\) of \(I\) consists of pairs \((m_{i},w_{i})\) for \(1\leq i\leq|V|\) and \((m_{i,j},w_{i,j})\) and \((m^{\prime}_{i,j},w^{\prime}_{i,j})\) for \((i,j)\in E\). Note that if we ignore the \"\(\cdot\cdot\)\" part in the above preference lists, each man is matched with the last woman and each woman is matched with the first man in \(M_{0}\). Hence these are the woman-oriented reduced lists with respect to \(I\) and \(M_{0}\), _i.e._, \(RL_{I,M_{0}}\). Clearly, the reduction can be performed in time polynomial in \(|G|\). To complete the proof, we show that \(G\) has an induced subgraph with \(k_{1}\) vertices and at least \(s\) edges if and only if there is a proper \(k_{2}\)-neighbor \(\tilde{I}\) of \(I\) such that \(MO(I)-MO_{I}(\tilde{I})\geq 2s\). Since \(k_{1}=k_{2}\), in the following we use \(k\) to denote \(k_{1}\) and \(k_{2}\) just for simplicity. First, suppose that \(G\) has an induced subgraph with \(k\) vertices and at least \(s\) edges, and let \(S(\subseteq V)\) be the set of those \(k\) vertices. Then, for each \(v_{i}\in S\), we modify \(m_{i}\)'s preference list by moving his man-optimal partner \(w_{i}\) to the top of the list, and let \(\tilde{I}\) be the resulting instance. We will show that, by doing this, \(m_{i,j}\) and \(m^{\prime}_{i,j}\)'s scores in the man-optimal stable matching of \(\tilde{I}\) are decreased by one respectively, if \(v_{i},v_{j}\in S\) and \((v_{i},v_{j})\in E\). Since there are at least \(s\) such edges, the score is decreased by at least \(2s\) in total. Recall that \(w_{i,j}\)'s reduced list in \(RL_{I,M_{0}}\) is \"\(m_{i,j}\)\(m_{i}\)\(m_{j}\)\(m^{\prime}_{i,j}\)\".