## 4 Hardness Results  
An SMI (Stable Marriage with Incomplete Lists) instance is just like an HR instance, only that all firms have capacity \(1\). Hence, all of its stable matchings have the same size. An SMTI (Stable Marriage with Ties and Incomplete Lists) instance is an SMI instance except that the participants' preference lists are allowed to contain ties. For this problem, a pair \((f,w)\) is a blocking pair of matching \(\mu\) if (i) \((f,w)\) is an acceptable pair; (ii) \(f\) has an opening or _f strictly_ prefers \(w\) to its only employee under \(\mu\); and (iii) \(w\) is unemployed or \(w\)_strictly_ prefers \(f\) to her employer under \(\mu\). Once again, a matching is (weakly) _stable_ if it has no blocking pairs. Unlike SMI instances, the stable matchings of an SMTI instance can have different sizes. In this section, we will show that certain kinds of SMTI instances can be encoded as HR+SN instances. This will allow us to translate hardness results known for max-SMTI, the problem of computing a maximum (cardinality) stable matching of an SMTI instance, to max-HR+SN. Let \(I\) be an SMTI instance. Suppose the ties in the preference lists of \(I\) are broken arbitrarily to create the SMI instance \(I^{\prime}\). Clearly, every stable matching of \(I^{\prime}\) is also a stable matching of \(I\). The converse, however, is not true. Let us say that the ties in \(I\) are _consistent_ if for every pair of participants \(q\) and \(q^{\prime}\), whenever \(q\) and \(q^{\prime}\) appear in the preference lists of \(p\) and \(p^{\prime}\), \(q\) and \(q^{\prime}\) are in a tie in the preference list of \(p\) if and only if they are also in a tie in the preference list of \(p^{\prime}\). In the next theorem, we show that when only the firms' preference lists contain ties and these ties are consistent, then the stable matchings of \(I\) can be retrieved from \(I^{\prime}\) by considering the locally stable matchings of \((I^{\prime},G)\), where \(G\) is constructed appropriately. **Theorem 5**. : _Let \(I\) be an SMTI instance where only the firms' preference lists contain ties, and the ties are consistent. Let \(I^{\prime}\) be the SMI instance obtained by breaking the ties in the preference lists of \(I\) arbitrarily. Let \(G\) be a graph such that whenever two workers \(w\) and \(w^{\prime}\) appear together in some firm's preference list in \(I\), \(w\) and \(w^{\prime}\) are adjacent if and only if they are not in a tie. Then the following are true: (i) Every stable matching of \(I\) is also a locally stable matching of \((I^{\prime},G)\). (ii) Every locally stable matching \(\mu^{\prime}\) of \((I^{\prime},G)\) can be transformed into a stable matching \(\mu\) of \(I\) such that \(|\mu|\geq|\mu^{\prime}|\) in time polynomial in the size of \(I\). Consequently, every maximum locally stable matching of \((I^{\prime},G)\) can be transformed into a maximum stable matching of \(I\) of the same size in time polynomial in \(|I|\)._  
Proof. : For (i), let \(\mu\) be a stable matching of \(I\). Suppose \(\mu\) is not a locally stable matching of \((I^{\prime},G)\), and \((f,w)\) is one of its local blocking pairs with \(w^{\prime}\) as a point of contact. Since \(f\) has capacity \(1\), \(w^{\prime}\) is the only employee of \(f\) and \(f\) prefers \(w\) over \(w^{\prime}\). In order for \((f,w)\) to not to be a blocking pair of \(\mu\) in \(I\), \(w\) and \(w^{\prime}\) must be in a tie in \(f\)'s preference list in \(I\). However, this cannot be the case--\(w\) and \(w^{\prime}\) are adjacent in \(G\) and ties are consistent in \(I\). Hence, \(\mu\) cannot have a local blocking pair in \((I^{\prime},G)\) and must therefore be a locally stable matching of the instance. For (ii), suppose \(\mu^{\prime}\) is a locally stable matching of \((I^{\prime},G)\). Let \((f,w)\) be a blocking pair of \(\mu^{\prime}\) in \(I\). Without loss of generality, assume that \(w\) is the worker that \(f\) prefers the most among those that form a blocking pair with \(f\). First, we note that \(f\) cannot be matched in \(\mu^{\prime}\).