## 3 The Easy Cases  
In this section, we present a family of HR+SN instances where finding a maximum locally stable matching can be solved in polynomial time. **Theorem 1**. : _Let \((I,G)\) be an HR+SN instance. Suppose that whenever two workers have a firm in common in their preference lists, the two workers also share an edge in \(G\). Then every stable matching of \(I\) is a maximum locally stable matching of \((I,G)\). Consequently, when \(G\) is the complete graph, every stable matching of \(I\) is a maximum locally stable matching of \((I,G)\)._  
Proof. : For now, assume that all firms in \(I\) have capacity \(1\). Suppose \((I,G)\) has a locally stable matching \(\sigma\) that is larger than the stable matchings of \(I\). Let \(\mu\) be one of these stable matchings. Then \(\sigma\bigoplus\mu\) has a \(\sigma\)-alternating path of the form \(f_{1},w_{1},f_{2},w_{2},\ldots,f_{k},w_{k}\) such that \((f_{i},w_{i})\in\sigma\) for \(i=1,\ldots,k\) and \((f_{i+1},w_{i})\in\mu\) for \(i=1,\ldots,k-1\). Since \(f_{1}\) is unmatched in \(\mu\), \(w_{1}\) must prefer \(f_{2}\) over \(f_{1}\); otherwise, \((f_{1},w_{1})\) is a blocking pair of \(\mu\). Now \(w_{1}\) and \(w_{2}\) both have \(f_{2}\) in their preference lists so they share an edge in \(G\). It must be the case then that \(f_{2}\) prefers \(w_{2}\) over \(w_{1}\); otherwise, \((f_{2},w_{1})\) is a local blocking pair of \(\sigma\). Continuing in this fashion, we have that for \(i=1,\ldots,k-1\), \(w_{i}\) prefers \(f_{i+1}\) over \(f_{i}\) because \(\mu\) is a stable matching of \(I\) while \(f_{i+1}\) prefers \(w_{i+1}\) over \(w_{i}\) because \(w_{i}\) and \(w_{i+1}\) are adjacent in \(G\) and \(\sigma\) is a locally stable matching of \((I,G)\). Consequently, \(f_{k}\) must prefer \(w_{k}\) over \(w_{k-1}\). However, \(w_{k}\) is unmatched in \(\mu\) so this implies that \((f_{k},w_{k})\) is a blocking pair of \(\mu\)--a contradiction. Hence, \(\sigma\) cannot exist, and \(\mu\) is a maximum locally stable matching of \((I,G)\). So suppose some firms in \(I\) have capacity greater than \(1\). Construct the HR+SN instance \((I^{(1)},G)\) from \((I,G)\). Notice that the property \"whenever two workers have a firm in common in their preference lists, the two workers also share an edge in \(G\)\" is preserved in \((I^{(1)},G)\). Let \(\sigma\) be a locally stable matching of \((I,G)\), and let \(\mu\) be a stable matching of \(I\). Consider their corresponding matchings \(\sigma^{(1)}\) and \(\mu^{(1)}\). From Proposition 2, \(\sigma^{(1)}\) is also a locally stable matching of \((I^{(1)},G)\). We also know that \(\mu^{(1)}\) is a stable matching of \(I^{(1)}\). If \(|\sigma|>|\mu|\), \(|\sigma^{(1)}|>|\mu^{(1)}|\). However, all firms in \(I^{(1)}\) have capacity \(1\), and according to the previous paragraph \(\mu^{(1)}\) is a maximum locally stable matching of \((I^{(1)},G)\). Hence, \(|\sigma|\leq|\mu|\), and \(\mu\) is a maximum locally stable matching of \((I,G)\). It is easy to see that, as a consequence of Proposition 4, if \(G\) is extended to a complete graph, the result still holds. The next theorem provides a bound that is different from the one presented in Proposition 3. It shows that when \(G\) is almost a complete graph, a stable matching of \(I\) and a maximum locally stable matching of \((I,G)\) will almost have the same size. **Theorem 2**. : _Let \((I,G)\) be an HR+SN instance. Suppose that the size of the largest matching in \(\bar{G}\), the complement of \(G\), is \(r\). Let \(\hat{\mu}\) be a maximum locally stable matching of \((I,G)\) and \(\mu\) be a stable matching of \(I\). Then \(|\hat{\mu}|\leq|\mu|+r\)._  
Proof. : Once again, let us begin the proof by assuming that all firms in \(I\) have capacity \(1\). First, notice that \(|\hat{\mu}|-|\mu|\) is bounded above by the number of \(\hat{\mu}\)-alternating paths in \(\hat{\mu}\bigoplus\mu\). Furthermore, the \(\hat{\mu}\)-alternating paths are vertex-disjoint.