## 4 Hardness Results
[13]) Suppose that in the SMTI-2 ML instance \(I\), there are \(n\) firms and \(n\) workers. Determining if \((I,G)\) has a stable matching of size \(n\) is NP-complete even if the ties occur in one master list only. The result holds even when (i) there is only one tie in that master list or (ii) all the ties are of length \(2\)._  
We now translate this result to HR+SN. **Theorem 6**. : _Suppose that in the HR+SN instance \((I,G)\), there are \(n\) firms and \(n\) workers, and each firm has capacity \(1\). Let \(K_{z}\) denote the complete graph on \(z\) vertices. Determining if \(I\) has a locally stable matching of size \(n\) is NP-complete, even when \(G\cong K_{n}-K_{n^{\prime}}\) where \(n^{\prime}<n\) or \(G\cong K_{n}-F\) where \(F\) is a matching in \(K_{n}\)._  
Proof. : Let \(I^{\prime}\) be an SMTI-2 ML instance with \(n\) firms and \(n\) workers, and the ties occur in one master list only. Without loss of generality, assume that it is the firms' master list of workers that contains the ties. Create the HR+SN instance \((I^{\prime\prime},G)\) according to Theorem 5. If there is an efficient algorithm for determining if \((I^{\prime\prime},G)\) has a locally stable matching of size \(n\), which is clearly a _maximum_ locally stable matching of \((I^{\prime\prime},G)\), then there is also an efficient algorithm for determining if \(I^{\prime}\) has a stable matching of size \(n\). However, Fact 1 states that the latter is an NP-complete problem. It follows that determining if \((I^{\prime\prime},G)\) has a locally stable matching of size \(n\) is also NP-complete. The form of \(G\) is based on Proposition 4, Fact 1 and Theorem 5. Next, we argue that max-HR+SN is NP-hard to approximate by appealing to the details of the following result of [PERSON] _et al._[14] with regards to approximating max-SMTI. **Fact 2**. : _([PERSON] et al. [14]) It is NP-hard to approximate max-SMTI within a factor of \(21/19-\delta\) for any constant \(\delta>0\)._  
**Theorem 7**. : _It is NP-hard to approximate max-HR+SN within a factor of \(21/19-\delta\) for any constant \(\delta>0\)._  
Proof. : To prove Fact 2, [PERSON] _et al._[14] relied on a result of [PERSON] and [PERSON] [15] about approximating a minimum vertex cover of a graph. Given a graph \(H=(V,E)\), we now describe how they constructed the SMTI instance \(I_{H}\). Note that we shall use firms in place of men and workers in place of women. For each vertex \(v_{i}\) of \(H\), create three firms \(v_{i}^{A},v_{i}^{B},v_{i}^{C}\), and three workers \(v_{i}^{a},v_{i}^{a},v_{i}^{c}\). Thus, there are a total of \(3|V|\) firms and \(3|V|\) workers. Suppose \(v_{i}\) is adjacent to \(d\) vertices \(v_{i_{1}},v_{i_{2}},\ldots,v_{i_{d}}\). Here are the preference lists of the firms and workers corresponding to \(v_{i}\):  
\[ \begin{array}{ccccccccc}v_{i}^{A}\colon&v_{i}^{a}&&&&v_{i}^{a}\colon&v_{i}^{ B}&v_{i_{1}}^{C}&\cdots&v_{i_{d}}^{C}&v_{i}^{A}\\ v_{i}^{B}\colon&(v_{i}^{a}&v_{i}^{b})&&&&v_{i}^{b}\colon&v_{i}^{B}&v_{i}^{C}&&\\ v_{i}^{C}\colon&v_{i}^{b}&v_{i_{1}}^{a}&\cdots&v_{i_{d}}^{a}&v_{i}^{C}&&v_{i}^{ C}\colon&v_{i}^{C}&&\end{array} \]  
Clearly, \(I_{H}\) can be constructed from \(H\) in time polynomial in the size of \(H\). Also, notice that the ties in \(I_{H}\) are consistent since \(v_{i}^{a}\) and \(v_{i}^{b}\) appear together in \(v_{i}^{B}\)'s preference list only. Using the reduction in Theorem 5, let \((I_{H}^{\prime},G)\) be the HR+SN instance that corresponds to \(I_{H}\). Let \(s^{+}(I_{H})\) and \(s^{+}(I_{H}^{\prime},G)\) denote the sizes of a maximum stable matching in \(I_{H}\) and a maximum locally stable matching in \((I_{H}^{\prime},G)\) respectively. According to Theorem 5, \(s^{+}(I_{H})=s^{+}(I_{H}^{\prime},G)\). Let \(\beta^{-}(H)\) denote the size of a minimum vertex cover of \(H\). They showed that \(s^{+}(I_{H})=3|V|-\beta^{-}(H)\). Since \(\beta^{-}(H)\) is NP-hard to approximate, it follows that \(s^{+}(I_{H})\) is also NP-hard to approximate.