## 2 Preliminaries  
In the stable matchings literature, the problem of finding a stable matching in the Arcaute-Vassilvitskii model sans the social network is often referred to as the Hospital/Residents problem (HR). The firms correspond to the hospitals while the workers correspond to the residents. In their seminal paper on stable matchings [10], [PERSON] and [PERSON] presented an algorithm that finds a stable matching for every HR instance \(I\). It can be implemented in \(O(|I|)\) time where \(|I|\) is the number of acceptable pairs in \(I\). In general, \(I\) can have many stable matchings. Nonetheless, [PERSON] and [PERSON] [11] showed that every stable matching of \(I\) has the same size and matches exactly the same set of residents. Throughout this paper, we shall assume that every HR instance we can consider has the property that a resident \(r\) is in a hospital \(h\)'s preference list if and only if \(h\) is also in \(r\)'s preference list. _An example._ In the following instance, let the hospitals be \(h_{1},h_{2},h_{3}\) whose capacities are \(2,2,4\) respectively. Let the set of residents be \(r_{1},r_{2},r_{3},r_{4},r_{5},r_{6},r_{7},r_{8}\). Here are their preference lists:  
\[ \begin{array}{ccccccccc}h_{1}\vdots&r_{1}&r_{2}&r_{5}&r_{6}&&r_{1}\vdots&h_ {1}&h_{3}&&r_{5}\vdots&h_{1}\\ h_{2}\vdots&r_{3}&r_{4}&r_{7}&r_{8}&&r_{2}\vdots&h_{1}&h_{3}&&r_{6}\vdots&h_{ 1}\\ h_{3}\vdots&r_{1}&r_{2}&r_{3}&r_{4}&&r_{3}\vdots&h_{2}&h_{3}&&r_{7}\vdots&h_{ 2}\\ \end{array} \]It is not difficult to see that \(\mu=\{(h_{1},r_{1}),(h_{1},r_{2}),(h_{2},r_{3}),(h_{2},r_{4})\}\) is a stable matching of the instance. It is, however, smaller than \(\sigma=\{(h_{1},r_{5}),(h_{1},r_{6}),(h_{2},r_{7}),(h_{2},r_{8}),(h_{3},r_{1}),( h_{3},r_{2}),\,(h_{3},r_{3}),\)\((h_{3},r_{4})\}\), which is a maximum matching of the instance. For HR instance \(I\), let \(B[I]\) denote the bipartite graph where the hospitals are the vertices on one side, and the residents on the other side. A pair \((h,r)\) is an edge if and only if they form an acceptable pair. Thus, every matching of \(I\) is a subgraph of \(B[I]\). Finding a maximum matching of \(I\) can be done by solving a maximum flow problem with \(B[I]\) as the \"base graph\": Create a source \(s\) and a directed edge from \(s\) to every hospital \(h\), and set its capacity to \(q_{h}\). Direct all edges \(\{h,r\}\) in \(B[I]\) from \(h\) to \(r\) and set its capacity to \(1\). Finally, create a sink \(t\) and a directed edge from every resident \(r\) to \(t\), and set its capacity to \(1\). There is a one-to-one correspondence between the maximum flows of this network and the maximum matchings of \(B[I]\). Let us suppose that all hospitals in \(I\) have capacity \(1\), and we wish to compare two of its matchings \(\mu\) and \(\sigma\). In this case, it is useful to consider their symmetric difference \(\mu\bigoplus\sigma\). In \(B[I]\), it is made up of what are called _alternating paths and cycles_--_i.e._, paths and cycles whose edges alternately belong to \(\mu\) and \(\sigma\). In cycles and even-length alternating paths, the number of \(\mu\)-edges and the number of \(\sigma\)-edges are the same; in odd-length alternating paths, the numbers differ by \(1\). Additionally, when \(|\sigma|>|\mu|\), there is at least one odd-length alternating path with one more \(\sigma\)-edge than \(\mu\)-edge. We shall call such a path a \(\sigma\)_-alternating path_. When not all hospitals in \(I\) have capacity \(1\), we can transform \(I\) to another instance where this is the case. Here is a standard trick [12]. Denote by \(I^{(1)}\) the instance obtained from \(I\) by doing the following: for each hospital \(h_{i}\) of \(I\) with capacity \(q_{h_{i}}\), replace \(h_{i}\) by \(q_{h_{i}}\) clones of \(h_{i}\): \(h_{i,1},h_{i,2},\ldots,h_{i,q_{h_{i}}}\). Let their capacities be \(1\), and let their preference lists be exactly the same as that of \(h_{i}\).