## 3 Changing One Man's Preference List
### Decision Variant  
Note that a direct application of Algorithm 1 solves PMI(1) in \(O(n^{3})\) time. We improve this to \(O(n^{2})\) using a structural property of stable matchings. Let \(I\) be an input. From the discussion in Section 3.1, it suffices to consider the instance \(I_{m}\) for each man \(m\) (see the description of Algorithm 1 for the definition of \(I_{m}\).) It is not hard to see that the man-optimal stable matching \(M_{0}\) of \(I\) is also stable in \(I_{m}\) for any \(m\). Hence, if \(M_{0}\) is not the man-optimal stable matching of \(I_{m}\) for some \(m\), then the man-optimal stable matching of \(I_{m}\) is better than \(M_{0}\), so the answer is \"yes\"; otherwise, the answer is \"no\". To check whether \(M_{0}\) is the man-optimal stable matching of \(I_{m}\) or not in time \(O(n)\) per man, we use the woman-oriented rotation digraphs defined in Section 2.2.  
Given \(I\), we construct the rotation digraph \(D_{I,M_{0}}\) with respect to the man-optimal stable matching \(M_{0}\). Clearly it is acyclic. For a man \(m\), we construct the instance \(I_{m}\) (defined before) and the rotation digraph \(D_{I_{m},M_{0}}\) (recall that \(M_{0}\) is stable in \(I_{m}\) and hence \(D_{I_{m},M_{0}}\) is defined). From the discussion in Section 2.2, we know that \(M_{0}\) is the man-optimal stable matching of \(I_{m}\) if and only if \(D_{I_{m},M_{0}}\) contains no cycle. Hence our task can be reduced to checking if \(D_{I_{m},M_{0}}\) contains a cycle. The pseudocode of our algorithm is given as Algorithm 2:  
```
1:Find the man-optimal stable matching \(M_{0}\) of \(I\).
2:Construct \(D_{I,M_{0}}\).
3:for each man \(m\)do
4: Modify \(I\) by moving \(M_{0}(m)\) to the top of \(m\)'s list. Let \(I_{m}\) be the resulting instance.
5: Construct \(D_{I_{m},M_{0}}\).
6:if\(D_{I_{m},M_{0}}\) contains a cycle then
7: Output \"yes\" and terminate.
8:endif
9:endfor
10:Output \"no\".
```  
**Algorithm 2**  
To construct the rotation digraph \(D_{I_{m_{1}},M_{0}}\), we remove an arc \((m_{5},m_{1})\) from \(D_{I,M_{0}}\) and add \((m_{5},m_{2})\) and obtain \(D_{I_{m_{1}},M_{0}}\) in Figure 2(c). Since \(D_{I_{m_{1}},M_{0}}\) contains a cycle, Algorithm 2 outputs \"yes\" and terminates.  
Lines 1 and 2 can be performed in time \(O(n^{2})\). Checking whether \(D_{I_{m},M_{0}}\) contains a directed cycle or not can be done by a standard topological sorting algorithm in time linear in the size of \(D_{I_{m},M_{0}}\). Since each vertex of \(D_{I_{m},M_{0}}\) has outdegree at most one, the size of \(D_{I_{m},M_{0}}\) is \(O(n)\) and line 6 can be done in \(O(n)\) time. Shortly, we show that \(D_{I_{m},M_{0}}\) can be constructed from \(D_{I,M_{0}}\) in time \(O(n)\). Then the overall time complexity of Algorithm 2 is \(O(n^{2})\).  
Note that the reduced lists \(RL_{I_{m},M_{0}}\) can be constructed from \(RL_{I,M_{0}}\) by deleting each woman \(w\) who precedes \(M_{0}(m)\) from \(m\)'s preference list, and correspondingly \(m\) from \(w\)'s list. If \(m\) is not \(next_{I,M_{0}}(w)\), then \(next_{I_{m},M_{0}}(w)=next_{I,M_{0}}(w)\). Otherwise, _i.e._, if \(next_{I,M_{0}}(w)=m\), then the man (say, \(m^{\prime}\)) at the third position of \(RL_{I,M_{0}}\) (if any) will be at the second position of \(RL_{I_{m},M_{0}}\), _i.e._, \(next_{I_{m},M_{0}}(w)=m^{\prime}\). Accordingly we must replace the directed edge \((M_{0}(w),m)\) by \((M_{0}(w),m^{\prime})\). By doing this for every such \(w\), we can obtain \(D_{I_{m},M_{0}}\) in time \(O(n)\).  
**Theorem 3.3**: _PMI(1) can be solved in \(O(n^{2})\) time._