## 2 Algorithm  
For a given instance of the problem let \(M_{opt}\) denote an optimal (_i.e._, largest) stable matching and let \(M,M^{\prime}\) be any two matchings. We say that \(e\) is an \(M\)-edge if \(e\in M\). A path \(P\) or a cycle \(C\) is called **alternating (w.r.t. \(M\))** if its edges alternate between \(M\)-edges and edges of \(E\backslash M\). It is well known from matching theory (see [13] for example) that \(M\oplus M^{\prime}\) disintegrates into a set of alternating paths and alternating cycles. (For two sets \(X,Y\), the set \(X\oplus Y\) denotes \((X\backslash Y)\cup\) (\(Y\backslash X\)).) Let \(S\) denote a set of maximal alternating paths and cycles of \(M\oplus M_{opt}\). Consider any alternating cycle \(C\) of \(S\) or any alternating path \(P\) of even length of \(S\). Then both \(C\) and \(P\) contain the same number of \(M\)-edges and \(M_{opt}\)-edges. Consider an alternating path \(P\) of length \(2k+1\) of \(S\). Then either \(\frac{|M_{opt}\cap P|}{|M\cap P|}=\frac{k+1}{k}\) or \(\frac{|M\cap P|}{|M_{opt}\cap P|}=\frac{k+1}{k}\). Therefore, if \(M\) is stable and \(S\) does not contain a path of length \(3\) with the middle edge being an \(M\)-edge, then \(|M_{opt}|\leq\frac{3}{2}|M|\) and \(M\) is a \(\frac{3}{2}\)-approximation of \(M_{opt}\). To achieve a \(\frac{3}{2}\)-approximation, we will eliminate such potential paths of length \(3\) of \(M\oplus M_{opt}\).  
Accordingly, we define a **dangerous path w.r.t. a matching**\(M\) to be an alternating path \(P=(w,m_{1},w_{1},m)\) such that \(w\) and \(m\) are unmatched in \(M\) (which means that \((m_{1},w_{1})\) is in \(M\) and \((w,m_{1}),(w_{1},m)\) do not belong to \(M\)) and \((m_{1},w_{1})\) is not a blocking pair for the matching \(N=\{(w,m_{1}),(w_{1},m)\}\). We need to concern ourselves only with dangerous paths w.r.t. a matching \(M\) that can be extended to a stable matching,_i.e._, \(M\) is such that there exists a stable matching \(M^{\prime}\) with \(M\subseteq M^{\prime}\). Therefore, if \(P=(w,m_{1},w_{1},m)\) is a dangerous path w.r.t. \(M\), then \(w\) and \(m_{1}\) do not form a blocking pair for \(M\), which means that \(w_{1}\) is at least as good for \(m_{1}\) as \(w\), and similarly, \(w_{1}\) and \(m\) do not form a blocking pair for \(M\), hence \(m_{1}\) is at least as good for \(w_{1}\) as \(m\). Since \((m_{1},w_{1})\) is not a blocking pair for the matching \(N=\{(w,m_{1}),(w_{1},m)\}\), either \(m_{1}\) is indifferent between \(w\) and \(w_{1}\) and then we say that \(P\) is a **masculine dangerous path**, or \(w_{1}\) is indifferent between \(m\) and \(m_{1}\) and then we say that \(P\) is a **feminine dangerous path**. A path \(P\) can of course be both a masculine and a feminine dangerous path.  
We also introduce the following terminology.  
* If man \(m\) is matched to woman \(w\) and there is at least one free woman \(w_{1}\) such that \(w\) and \(w_{1}\) are equally good for \(m\), then we say that \(w_{1}\) is a **satellite** of \(m\) and \(m\) is **satellite**.
* If woman \(w\) is matched to a satellite man \(m\), then we say that \(w\) is **co-satellite**.
* If \(e=(m,w)\) is such that \(w\) is free and there is at least one free woman \(w_{1}\
eq w\) such that \(w\) and \(w_{1}\) are equally good for \(m\), then \(e\) is called **special**, and consequently, \((m,w_{1})\) is also called special.
* If man \(m\) has at least one free woman incident with him, then he is said to be **subsatellitic**.
* Woman \(w\) matched to a subsatellitic man \(m\) and not co-satellite is said to be **co-subsatellitic w.r.t.**\(m^{\prime}\) if \(m\) and \(m^{\prime}\) are equally good for her.  
Figure 1 illustrates the notions introduced above.  
Let us notice that if a free man \(m\) has a co-satellite woman \(w\) on his list, then it is possible that he belongs to a masculine dangerous path, and analogously, if a free man \(m\) has a woman \(w\) on his list who is co-subsatellitic with respect to him, then it is possible that he belongs to a feminine dangerous path.