Stable Marriage and Roommates Problems with Restricted Edges: Complexity and Approximability

The strongest positive case is that this paper has two genuine population-facing objectives—blocking and restricted-edge violations—and both survive as meaningful mass-optimization problems. The paper itself is entirely discrete: its agents are named, and its matchings are integral. That is not a novelty collision.

The natural regime is a large matching market with repeated agent classes. On the marriage side, applicants and positions may be grouped by qualification, location, specialty, or contract type; on the roommates side, people may be grouped by schedule, budget, accessibility, and living preferences. A type is a complete preference-and-restriction profile. If \(N\) agents are distributed among \(\tau\) types, the intended regime is \(N\gg \tau\), with the type masses \(\mu_t\) rational and given directly.

For a marriage instance, let \(A\) and \(B\) be the man and woman types, with masses \(\mu_a\) and \(\nu_b\). A solution is a mass matching \(x=(x_{ab})\), where \(x_{ab}\) is the mass of type \(a\) matched to type \(b\), subject to

\[ \sum_b x_{ab}\le \mu_a,\qquad \sum_a x_{ab}\le \nu_b. \]

Thus \(x\) may be fractional at type level, while every infinitesimal agent still receives one integral partner. Forbidden pairs impose \(x_{ab}=0\); a forced pair can impose a lower mass bound \(x_{ab}\ge \ell_{ab}\).

My lead anchor is Theorem 3.5. It is proved in this paper, although its reduction uses the cited hardness of Exact Maximal Matching.

Theorem 3.5 states that each of \({\sc min\ bp\ sm\ forbidden}\) and \({\sc min\ bp\ sm\ forced}\) is not approximable within a factor of \(n^{1-\varepsilon}\), for any \(\varepsilon>0\), unless \(\mathrm{P}=\mathrm{NP}\). The result remains true when all preference lists are complete. Here the problem must satisfy all forbidden or forced-edge constraints while minimizing the number of blocking edges.

The corresponding continuous problem is:

\[ \textsc{Min-Blocking-Mass}_{\infty}\text{-SM-Restricted}. \]

Given type masses, complete strict rankings over counterpart types, and forbidden or forced type-pair mass constraints, find a mass matching \(x\) satisfying those restrictions and minimizing total blocking mass.

For a type \(a\) and possible partner type \(b\), define

\[ D_a(b;x) = \left(\mu_a-\sum_{b'}x_{ab'}\right) + \sum_{b'\succ_a b}x_{ab'}. \]

This is the mass of type \(a\) that is unmatched or matched to a type it likes less than \(b\). Define \(D_b(a;x)\) symmetrically, and let

\[ \beta_{ab}(x)=\min\{D_a(b;x),D_b(a;x)\}. \]

The quantity \(\beta_{ab}(x)\) is the largest mass that could mutually improve by moving onto pair \(ab\). The objective is

\[ \Phi(x)=\sum_{ab}\beta_{ab}(x). \]

A solution consists of the optimal mass matrix \(x\), together with the induced blocking masses. When every type has mass \(1/N\), multiplying by \(N\) recovers the ordinary number of blocking pairs in a repeated finite market.

I would expect this problem to belong to Class B in its general form: the hardness is likely to survive rather than disappear. After clearing denominators, the feasible mass-matchings form a transportation polytope with integral extreme points. Moreover, \(\Phi\) is concave and piecewise linear, since it is a sum of minima of affine functions; a minimum of a concave function over a polytope has an optimum at an extreme point. This suggests that an optimal continuous solution can be chosen with integral scaled mass, so fractional population mass may not evade the paper’s combinatorial obstruction. The precise open question is whether the reduction behind Theorem 3.5 can be made type-compressed while keeping \(N\gg\tau\), and whether the \(n^{1-\varepsilon}\) gap survives in \((\tau,\log N)\)-complexity.

The second anchor is Theorem 4.2, also proved in this paper. It states that both \({\sc sr\ min\ forbidden\ dec}\) and \({\sc sr\ max\ forced\ dec}\) are \(\mathrm{NP}\)-complete. The first asks whether a stable roommates instance has a stable matching containing at most \(K\) forbidden edges. The second asks whether it has a stable matching omitting at most \(K\) forced edges. The reduction is from Vertex Cover.

The continuous counterpart is:

\[ \textsc{Min-Restricted-Violation-Mass}_{\infty}\text{-SR}. \]

Here \(T\) is a finite set of roommate types with masses \(\mu_t\), strict rankings over acceptable types, and symmetric mass-matching variables \(x_{st}=x_{ts}\). Let

\[ u_t=\mu_t-\sum_s x_{ts} \]

be unmatched mass, and define

\[ D_t(s;x)=u_t+\sum_{r\succ_t s}x_{tr}. \]

The mass matching is stable in the atomless sense if, for every acceptable pair \(\{s,t\}\),

\[ \min\{D_s(t;x),D_t(s;x)\}=0. \]

That is exactly the statement that no positive mass on both sides mutually prefers one another to its current assignment. The optimization objective is

\[ V(x)= \sum_{\{s,t\}\in P}x_{st} + \sum_{\{s,t\}\in Q}(\ell_{st}-x_{st})_+. \]

The forbidden-only decision question asks whether a stable mass matching has \(V(x)\le K\); the forced-only version asks the same with only the second term present. A solution is the stable mass matrix minimizing \(V\), not merely a fractional encoding of a matching.

I would tentatively classify this exact atomless version as Class C, or at least as an important boundary problem. Each stability requirement is a disjunction,

\[ D_s(t;x)=0 \quad\text{or}\quad D_t(s;x)=0, \]

so the feasible region is a union of many polyhedra rather than one LP. The paper’s discrete \(\mathrm{NP}\)-hardness may transfer if an integrality theorem is found; otherwise the disjunctive structure itself would give a continuum-specific source of hardness. Either outcome is valuable. A natural follow-up is the ex-ante relaxation in which one replaces these disjunctions by the standard linear fractional-stability inequalities. That version is immediately an LP, giving a clean test of whether the paper’s hardness is caused by integral stability or by the underlying preference structure.

As a useful control, Theorem 4.1 gives the opposite side of the paper’s landscape. It is proved here, using the known polynomial algorithm for minimum-weight stable marriage. The theorem states that \({\sc sm\ min\ restricted\ violations}\) is solvable in polynomial time: assign weight \(-1\) to forced edges, \(0\) to unrestricted edges, and \(1\) to forbidden edges, then find a minimum-weight stable marriage.

Its continuous mirror is:

\[ \textsc{Min-Restricted-Violation-Mass}_{\infty}\text{-SM}. \]

Use the same type masses and mass variables \(x_{ab}\), but impose the fractional stable-marriage constraints

\[ x_{ab} +\sum_{b'\succ_a b}x_{ab'} +\sum_{a'\succ_b a}x_{a'b} \ge \min\{\mu_a,\nu_b\} \]

for every acceptable type pair, together with the mass-conservation constraints. Minimize

\[ \sum_{ab\in P}x_{ab} + \sum_{ab\in Q}(\ell_{ab}-x_{ab})_+. \]

This is a linear program after the forced lower bounds are represented in the usual way, so I would expect Class A: polynomial time in the number of types and the encoding length of the masses. In the bipartite case, the fractional object also has a natural ex-post interpretation as the aggregate of stable integral matchings in the denominator-cleared market. Thus this is not merely “make the matching fractional”; it is the high-multiplicity version of the paper’s underlying restricted stable-matching problem.

Together these mirrors cover the paper’s main contribution: case BP for Stable Marriage, and case CV for both Stable Marriage and Stable Roommates. They do not claim to continuize the paper’s degree bounds or its ordinary finite-agent algorithms. The central research questions become whether blocking-mass minimization preserves the paper’s hardness, whether stable-roommates violation minimization is genuinely continuum-specific, and whether the bipartite case collapses to an LP.

The weakest point is unavoidable: the paper assumes strict preferences over named individuals, whereas a high-multiplicity population naturally has strict preferences over types and anonymity within a type. If identity-specific tie-breaking is essential to the authors’ notion of stability, then the type model changes the problem. I would defend the mirror by treating within-type identity as economically irrelevant administrative tie-breaking, and by noting that the unit-mass special case recovers the paper exactly. But proving that this convention is acceptable—and determining whether the exact atomless and ex-ante notions coincide in the bipartite case—is part of the programme, not something the paper settles.