Answer: \(\mathrm{NP}\)-complete, even with equal dyadic masses and preference lists of length at most three.
Theorem 4.2 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximate{\sc sr min forbidden dec} and {\sc sr max forced dec} are $\NP$-complete.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given roommate types \(T\) with rational masses \(\mu_t\), anonymous strict rankings of acceptable types, and forbidden type pairs \(P\), choose symmetric matching masses \(x_{st}\ge0\) with \(\sum_s x_{st}\le\mu_t\). Define \(D_t(s;x)=\mu_t-\sum_r x_{tr}+\sum_{r\succ_t s}x_{tr}\), require \(\min\{D_s(t;x),D_t(s;x)\}=0\) for every acceptable pair, and decide whether some such \(x\) satisfies \(\sum_{\{s,t\}\in P}x_{st}\le K\).
A society is given by its support: a list \(T\) of \(\tau\) types with positive binary-rational masses \(\mu_t\), normalized by \(\sum_{t\in T}\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types.
An undirected, loopless acceptability graph \((T,E)\) specifies mutually acceptable type pairs; let \(m=|E|\). Each type strictly ranks its neighbors, identically for all individuals of that type, and prefers every acceptable partner to being unmatched. Write \(s\succ_t r\) when type \(t\) prefers \(s\) to \(r\).
The input also contains forbidden pairs \(P\subseteq E\) and a positive binary-rational threshold \(K\). Let \(L\) be the total input bit length.
A matching consists of real masses \(x_{st}=x_{ts}\geq0\), with \(x_{st}=0\) outside \(E\) and \(\sum_{s\in T}x_{st}\leq\mu_t\) for every \(t\). Each cross-type pair mass consumes that mass at both endpoints; within-type matching is excluded.
For \(\{s,t\}\in E\), define the mass willing to switch to type \(s\) by \(D_t(s;x)=\mu_t-\sum_{r\in T}x_{tr}+\sum_{r:\,s\succ_t r}x_{tr}\). Require \(\min\{D_s(t;x),D_t(s;x)\}=0\) for every acceptable pair, including forbidden pairs.
The decision problem asks whether such a stable matching exists with \(\sum_{\{s,t\}\in P}x_{st}\leq K\), counting each unordered pair once.
Is this continuous forbidden-mass decision problem solvable in polynomial time in \(m,\tau,L\), or is it \(\mathrm{NP}\)-hard?
For discrete strict-preference roommates, deciding whether a stable matching uses at most a given number of forbidden edges is \(\mathrm{NP}\)-complete, even with preference lists of length at most three ([Cseh–Manlove](https://arxiv.org/pdf/1412.0271)).
For unit-capacity fractional roommates, maximizing welfare under ordinal stability is \(\mathrm{NP}\)-hard even with strict preferences; this uses a different objective ([Chen–Roy–Sorge](https://www.ijcai.org/proceedings/2021/0013.pdf)). No result settling this exact forbidden-mass problem was located.
The continuous forbidden-mass decision problem is \(\mathrm{NP}\)-complete, even when all type masses are equal dyadic rationals and every preference list has length at most three.
The proof below treats real-valued matchings directly; it does not assume that fractional solutions can be rounded to discrete stable matchings.
For an acceptable pair \(\{s,t\}\), define
\(B_t(s)=\{s\}\cup\{r:r\succ_t s\}\).
Since preferences are strict, partitioning the neighbors of \(t\) into those better than \(s\), \(s\) itself, and those worse than \(s\) gives
\(D_t(s;x)=\mu_t-\sum_{r\in B_t(s)}x_{tr}\).
Capacity feasibility implies \(D_t(s;x)\geq 0\). Thus stability on \(\{s,t\}\) is exactly the disjunction
\(\sum_{r\in B_t(s)}x_{tr}=\mu_t\)
or
\(\sum_{r\in B_s(t)}x_{sr}=\mu_s\).
We will use this identity both in the reduction and in proving membership in \(\mathrm{NP}\).
We reduce from vertex cover on simple cubic graphs: given \(G=(V,F)\) and an integer \(k\), decide whether there is \(C\subseteq V\) with \(|C|\leq k\) meeting every edge. This problem is \(\mathrm{NP}\)-complete; it is also the source problem used in the proof of [Cseh–Manlove, Theorem 4.8](https://arxiv.org/pdf/1412.0271).
Write \(V=\{v_1,\ldots,v_n\}\). We may restrict to \(1\leq k\leq n\), since thresholds outside this range are trivially decidable and can be mapped to fixed yes or no instances within the range.
For each \(v_i\), introduce six types
\(p_i^1,q_i^1,p_i^2,q_i^2,p_i^3,q_i^3\).
Superscripts are interpreted cyclically modulo three.
Add the six internal edges
\(\{p_i^r,q_i^r\}\) and \(\{q_i^r,p_i^{r+1}\}\), for \(r\in\{1,2,3\}\).
Assign the three edges incident to \(v_i\) bijectively to its three types \(p_i^1,p_i^2,p_i^3\). For every source edge \(\{v_i,v_j\}\), add an external edge between its assigned types at the two endpoints. Consequently, each \(p_i^r\) has exactly one external neighbor; denote it by \(z_i^r\).
The preference lists are:
These lists are strict and have length at most three.
Choose the smallest power of two \(N\) satisfying \(N\geq 6n\), and add \(N-6n\) isolated types. Give every type mass \(c=1/N\). There are exactly \(N\) types, so their masses sum to one. All masses are positive dyadic rationals.
Finally, set
\(P=\{\{p_i^1,q_i^1\}:1\leq i\leq n\}\)
and \(K=kc\).
The construction has \(\tau=N<12n\) types and \(m=6n+|F|\) edges. Its size and construction time are polynomial in the source input length.
Fix any stable matching \(x\) in the constructed society. For each gadget, write
\(a_i^r=x_{p_i^rq_i^r}\),
\(b_i^r=x_{q_i^rp_i^{r+1}}\), and
\(h_i^r=x_{p_i^rz_i^r}\).
The capacity constraints are
\(a_i^r+b_i^r\leq c\)
at \(q_i^r\), and
\(a_i^r+b_i^{r-1}+h_i^r\leq c\)
at \(p_i^r\).
Consider \(\{p_i^r,q_i^r\}\). Type \(p_i^r\) ranks \(q_i^r\) first, while \(q_i^r\) ranks \(p_i^r\) last. Therefore,
\(D_{p_i^r}(q_i^r;x)=c-a_i^r\)
and
\(D_{q_i^r}(p_i^r;x)=c-a_i^r-b_i^r\).
Both quantities are nonnegative, and the second is no larger than the first. Their minimum can therefore be zero only if
\(a_i^r+b_i^r=c\).
Thus every \(q_i^r\) is saturated.
Summing the three capacity inequalities at the \(p\)-types of gadget \(i\) gives
\(\sum_{r=1}^3(a_i^r+b_i^{r-1})+\sum_{r=1}^3h_i^r\leq 3c\).
Cyclic reindexing and the preceding equalities yield
\(\sum_{r=1}^3(a_i^r+b_i^{r-1})
=\sum_{r=1}^3(a_i^r+b_i^r)=3c\).
Hence \(\sum_{r=1}^3h_i^r=0\). Nonnegativity implies \(h_i^r=0\) for every \(r\). Moreover, the three \(p\)-capacity inequalities must all be tight, so
\(a_i^r+b_i^{r-1}=c\).
Comparing this equality with \(a_i^r+b_i^r=c\) gives \(b_i^r=b_i^{r-1}\). Consequently, there is a single parameter \(a_i\in[0,c]\) such that, throughout gadget \(i\),
\(a_i^r=a_i\) and \(b_i^r=c-a_i\).
Thus every stable matching saturates all six types of every gadget, carries zero mass on every external edge, and has this one-parameter internal form.
Consider the external edge representing \(\{v_i,v_j\}\), joining \(p_i^r\) to \(p_j^s\).
Type \(p_i^r\) is saturated. Its only partner worse than its external neighbor is \(q_i^{r-1}\), with matching mass \(c-a_i\). Therefore,
\(D_{p_i^r}(p_j^s;x)=c-a_i\).
Likewise,
\(D_{p_j^s}(p_i^r;x)=c-a_j\).
Stability of this external edge is consequently equivalent to
\(a_i=c\) or \(a_j=c\).
In particular,
\(C_x=\{v_i:a_i=c\}\)
is a vertex cover of \(G\).
Only one edge per gadget is forbidden, and its mass is \(a_i\). Thus the forbidden mass is
\(\sum_{\{s,t\}\in P}x_{st}=\sum_{i=1}^n a_i\).
Every vertex in \(C_x\) contributes exactly \(c\), while all other contributions are nonnegative. Hence
\(c|C_x|\leq\sum_{i=1}^n a_i\).
If the matching satisfies the threshold, then
\(c|C_x|\leq kc\), and therefore \(|C_x|\leq k\).
Conversely, let \(C\) be a vertex cover with \(|C|\leq k\). Set \(a_i=c\) when \(v_i\in C\), and \(a_i=0\) otherwise. For every \(r\), assign
\(x_{p_i^rq_i^r}=a_i\)
and
\(x_{q_i^rp_i^{r+1}}=c-a_i\).
Set every external edge mass to zero.
Every gadget type has total incident mass \(c\), so all capacity constraints hold. The isolated types remain unmatched.
We check every acceptable edge:
These checks include the forbidden edges. Thus the matching is stable, and its forbidden mass is \(c|C|\leq kc=K\).
We have proved the required equivalence: \(G\) has a vertex cover of size at most \(k\) if and only if the constructed society has a stable matching of forbidden mass at most \(K\). This establishes \(\mathrm{NP}\)-hardness.
More precisely, the minimum forbidden mass in the constructed instance equals \(c\) times the minimum vertex-cover size. Fractional gadget parameters cannot improve this optimum.
Although matching masses may be real, every yes instance has a rational witness of polynomial bit length.
Given a feasible stable real matching, choose, for every acceptable edge, an endpoint at which the willingness to switch is zero. Fixing these choices produces a rational linear system consisting of:
There are \(m\) variables and polynomially many constraints. Every coefficient is in \(\{-1,0,1\}\), and every right-hand side is zero, a mass, or \(K\).
The resulting polytope is nonempty because it contains the original real matching. It is bounded because each edge variable lies between zero and one. Therefore it has a vertex.
For completeness, its vertex coordinates have polynomial bit length. Let \(Q\) be the product of the denominators appearing in the masses and \(K\); its bit length is \(O(L)\). At a vertex, choose \(m\) linearly independent tight constraints, with coefficient matrix \(A\). The matrix has integer entries of absolute value at most one. Hadamard’s inequality bounds \(|\det A|\) by \(m^{m/2}\). Applying Cramer’s rule after multiplying the right-hand side by \(Q\) shows that each coordinate has numerator and denominator bit length \(O(L+m\log(m+1))\).
This rational vertex satisfies the chosen zero-willingness equalities and hence all original stability conditions. A verifier can check capacities, the threshold, and stability using exact rational arithmetic in polynomial time. The case \(m=0\) is immediate.
Thus the problem belongs to \(\mathrm{NP}\). Together with the reduction, this proves \(\mathrm{NP}\)-completeness, and rules out a polynomial-time algorithm in \(m,\tau,L\) unless \(\mathrm{P}=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The prover’s claim is proved. The reduction applies directly to real-valued matchings, and the rational-witness argument establishes membership in \(\mathrm{NP}\). I found no major or minor mathematical issues.
For an acceptable pair \(\{s,t\}\), strict preferences partition the neighbors of \(t\) into those better than \(s\), \(s\) itself, and those worse than \(s\). Substituting this partition into the given definition yields exactly
\[
D_t(s;x)=\mu_t-\sum_{r\in B_t(s)}x_{tr}.
\]
Capacity feasibility and nonnegativity imply that this expression is nonnegative. Therefore the minimum of the two willingness quantities is zero exactly when at least one of the stated endpoint equalities holds. This equivalence applies to forbidden edges as well.
The cited source is appropriate: the proof of [Cseh–Manlove, Theorem 4.8](https://arxiv.org/pdf/1412.0271) explicitly uses the NP-completeness of vertex cover on cubic graphs. The prover states the source decision problem and uses its degree-three hypothesis to assign exactly one external edge to each \(p\)-type.
The restriction to nontrivial thresholds \(1\leq k\leq n\) preserves hardness: thresholds outside this range are decidable immediately on nonempty cubic graphs. In particular, the constructed threshold \(K=kc\) is positive.
The six internal edges in each gadget are distinct and loopless. External edges join types in different gadgets. Since the source graph is simple, the construction introduces no repeated external edges. Every \(p\)-type has three distinct neighbors, and every \(q\)-type has two; the stated rankings are strict.
Choosing the least power of two \(N\geq6n\) gives \(6n\leq N<12n\). The padding types are isolated, all masses equal the positive dyadic rational \(1/N\), and their total is one. The counts \(\tau=N\) and \(m=6n+|F|\) are correct. Both \(c\) and \(K\) have polynomial encoding length.
On \(\{p_i^r,q_i^r\}\), the two willingness quantities are exactly
\[
c-a_i^r
\quad\text{and}\quad
c-a_i^r-b_i^r.
\]
Capacity feasibility makes both nonnegative, and nonnegativity of \(b_i^r\) makes the second no larger than the first. Thus their minimum is the second quantity. Stability forces
\[
a_i^r+b_i^r=c.
\]
This deduction holds for arbitrary real matching masses.
Summing the three \(p\)-capacity inequalities counts each internal \(a\)-mass and \(b\)-mass once. Cyclic reindexing and the preceding saturation equalities make their total \(3c\). Consequently the sum of the nonnegative external masses is at most zero, so every \(h_i^r\) vanishes.
The remaining three capacity inequalities have left-hand sides summing to \(3c\), with each bounded above by \(c\). Hence each is tight:
\[
a_i^r+b_i^{r-1}=c.
\]
Comparing this with \(a_i^r+b_i^r=c\) forces all three \(b\)-masses to agree, and therefore all three \(a\)-masses to agree. The parameter range \(a_i\in[0,c]\) follows from nonnegativity.
These are necessary conditions for every stable matching. The argument does not incorrectly assume that arbitrary parameters satisfying this form automatically satisfy external stability.
Each \(p_i^r\) is saturated, and its only neighbor ranked below its external neighbor is \(q_i^{r-1}\). Its willingness on the external edge is therefore exactly \(c-a_i\). At the other endpoint it is \(c-a_j\).
Both quantities are nonnegative, so stability is equivalent to
\[
a_i=c\quad\text{or}\quad a_j=c.
\]
Consequently \(C_x=\{v_i:a_i=c\}\) meets every source edge. Parameters strictly between zero and \(c\) do not qualify as covering vertices; the proof handles this distinction correctly.
There is precisely one forbidden edge per gadget, carrying mass \(a_i\). Thus the objective counts each unordered forbidden pair once and equals \(\sum_i a_i\). Every member of \(C_x\) contributes exactly \(c\), while the remaining contributions are nonnegative. The inequality
\[
c|C_x|\leq\sum_i a_i\leq kc
\]
therefore implies \(|C_x|\leq k\).
Conversely, the matching constructed from a vertex cover satisfies every gadget capacity with equality. All acceptable edge classes are checked:
Isolated types have no stability constraints. The checks include forbidden edges, and the forbidden mass is exactly \(c|C|\). This establishes the claimed decision equivalence. The stronger equality between the two optimum values also follows from the same two bounds.
Starting from a stable real matching, choosing a zero-willingness endpoint for each edge produces a nonempty rational polytope. Its constraints include the original capacities and threshold, so any point satisfying the chosen equalities remains feasible and stable.
Each edge variable is bounded by an endpoint mass, which is at most one by normalization. The polytope is therefore bounded and has a vertex. At a vertex with \(m>0\), the active constraint normals span the variable space, permitting the stated selection of \(m\) independent tight constraints.
The selected matrix has integer entries of absolute value at most one. Hadamard’s bound applies because every row has Euclidean norm at most \(\sqrt m\). The denominator product \(Q\) has bit length \(O(L)\); multiplying the selected right-hand side by \(Q\) makes it integral. Cramer’s rule, including the corresponding cofactor bounds for the numerators, gives polynomial coordinate bit length as claimed.
Exact rational arithmetic can verify capacities, stability, and the threshold in polynomial time. The separately noted case \(m=0\) is immediate: there are no acceptable or forbidden edges, and the zero matching is feasible.
No repair or additional clarification is needed. The proof establishes \(\mathrm{NP}\)-completeness for the exact continuous forbidden-mass problem, including the claimed equal-dyadic-mass and preference-length restrictions. Its exclusion of a polynomial-time algorithm is correctly conditional on \(\mathrm{P}\ne\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.