Dias et al. (2003) gave a polynomial-time algorithm to decide whether such a solution exists in the presence of restricted edges. If the answer is no, one might look for a solution close to optimal. Since optimality in this context means that the matching is stable and satisfies all constraints on restricted pairs, there are two ways of relaxing the constraints by permitting a solution to: (1) be blocked by as few as possible pairs, or (2) violate as few as possible constraints n restricted pairs.
Our main theorems prove that for the (bipartite) Stable Marriage problem, case (1) leads to -hardness and inapproximability results, whilst case (2) can be solved in polynomial time. For non-bipartite Stable Roommates instances, case (2) yields an -hard but (under some cardinality assumptions) 2-approximable problem. In the case of -hard problems, we also discuss polynomially solvable special cases, arising from restrictions on the lengths of the preference lists, or upper bounds on the numbers of restricted pairs.