Answer: \(\mathrm{NP}\)-complete and \(\mathrm{FPT}\) parameterised by \(\tau\), with exact running time \(2^{|E|+\tau}L^{O(1)}\leq 2^{m(\tau-m)+\tau}L^{O(1)}=2^{O(\tau^2)}L^{O(1)}\). Hardness holds already for unit masses and \(b=0\).
Theorem 13 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateTYPED MAX SIZE MIN BP SMTI belongs to FPT when parameterised by the number k of different types in the given instance.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finite applicant types \(I\), position types \(J\), rational masses \(\mu_i,\nu_j\), and their weak preferences and acceptability, choose an assignment-mass matrix \(x\) with \(x_{ij}\ge 0\), \(x_{ij}=0\) for unacceptable pairs, and row and column sums bounded by \(\mu_i\) and \(\nu_j\); maximize \(\sum_{ij}x_{ij}\), then minimize \(B(x)=\sum_{(i,j)\text{ mutually acceptable}} A_{ij}(x)C_{ij}(x)\), where \(A_{ij}(x)=\mu_i-\sum_{j'}x_{ij'}+\sum_{j':\,j\succ_i j'}x_{ij'}\) and \(C_{ij}(x)=\nu_j-\sum_{i'}x_{i'j}+\sum_{i':\,i\succ_j i}x_{i'j}\).
Let \(I\) and \(J\) be nonempty, disjoint sets of applicant and position types. A society is given by its support: the list of its \(\tau=|I|+|J|\) types with positive binary-rational masses \(\mu_i,\nu_j\); \(\tau\) counts listed types, not possible types. Masses need not sum to one, and the two sides may have unequal total mass.
Each type has a weak preference order over acceptable opposite-side types; individuals within a type are indistinguishable. Let \(E\subseteq I\times J\) contain the mutually acceptable pairs, with every type incident to at least one pair. Every acceptable partner is strictly preferred to being unmatched; ties are retained, and \(\succ\) denotes strict preference.
A feasible assignment is a real matrix \(x\geq0\) with \(x_{ij}=0\) outside \(E\), \(\sum_{j\in J}x_{ij}\leq\mu_i\), and \(\sum_{i\in I}x_{ij}\leq\nu_j\). Write \(S^*=\max_x\sum_{(i,j)\in E}x_{ij}\).
For \((i,j)\in E\), define \(A_{ij}(x)=\mu_i-\sum_{j'\in J}x_{ij'}+\sum_{j'\in J:\,j\succ_i j'}x_{ij'}\) and \(C_{ij}(x)=\nu_j-\sum_{i'\in I}x_{i'j}+\sum_{i'\in I:\,i\succ_j i'}x_{i'j}\); preference-restricted sums range over acceptable types.
Define \(B(x)=\sum_{(i,j)\in E}A_{ij}(x)C_{ij}(x)\). Given a binary-rational threshold \(b\geq0\), decide whether a feasible \(x\) satisfies \(\sum_{(i,j)\in E}x_{ij}=S^*\) and \(B(x)\leq b\).
Is this decision problem in \(\mathrm{P}\) or NP-hard? If NP-hard, is it FPT parameterised by \(\tau\)? State running times in \(m=|J|\), \(\tau\), and the total input bit length \(L\), including the threshold.
The discrete maximum-cardinality, minimum-blocking-pairs problem is FPT parameterised by the number of types ([Meeks–Rastegari](https://eprints.gla.ac.uk/222769/7/222769.pdf)), but NP-hard even with strict preferences ([Biró–Manlove–Mittal](https://eprints.gla.ac.uk/5930/1/minbp.pdf)).
No result settling this exact continuous decision problem was located.
The stated decision problem is \(\mathrm{NP}\)-complete and fixed-parameter tractable parameterised by \(\tau\).
Writing \(d=|E|\), an exact algorithm runs in
\[
2^{d+\tau}L^{O(1)}
\;\leq\;
2^{m(\tau-m)+\tau}L^{O(1)}
\;=\;
2^{O(\tau^2)}L^{O(1)}.
\]
The exponent hidden in \(L^{O(1)}\) is an absolute constant. All running times below count bit operations, and \(L\) includes the threshold.
The hardness result already holds when every mass equals \(1\), the two sides have equal size, the acceptability graph has a perfect matching, and \(b=0\). The reduction uses ties.
For every feasible assignment \(x\), each \(A_{ij}(x)\) is the sum of unmatched applicant mass and applicant mass assigned to partners strictly worse than \(j\). Thus \(A_{ij}(x)\geq0\). Similarly, \(C_{ij}(x)\geq0\).
Consequently,
\[
B(x)=0
\quad\Longleftrightarrow\quad
\text{for every }(i,j)\in E,\quad
A_{ij}(x)=0\ \text{or}\ C_{ij}(x)=0.
\]
This equivalence will allow a zero-blocking fractional assignment to be rounded without introducing a blocking pair.
Lemma. Suppose \(|I|=|J|=n\), all masses equal \(1\), and \(x\) is feasible with total assigned mass \(n\). If \(B(x)=0\), then the positive support of \(x\) contains a weakly stable perfect matching.
Here, weak stability means that no mutually acceptable pair strictly prefers each other to their assigned partners.
Proof. The total row capacity and total column capacity both equal \(n\). Since \(x\) assigns total mass \(n\), every row and every column sums to \(1\).
Let
\[
H=\{(i,j)\in E:x_{ij}>0\}.
\]
For any \(U\subseteq I\), let \(N_H(U)\) be its neighbourhood in \(H\). Then
\[
|U|
=
\sum_{i\in U}\sum_jx_{ij}
=
\sum_{j\in N_H(U)}\sum_{i\in U}x_{ij}
\leq
\sum_{j\in N_H(U)}\sum_{i\in I}x_{ij}
=
|N_H(U)|.
\]
Hence Hall’s condition holds. Hall’s theorem gives a matching \(M\subseteq H\) covering \(I\); because the sides have equal size, \(M\) is perfect.
Consider any \((i,j)\in E\). Since \(B(x)=0\), at least one of \(A_{ij}(x)\) and \(C_{ij}(x)\) vanishes.
If \(A_{ij}(x)=0\), row saturation gives
\[
0=A_{ij}(x)
=\sum_{j':\,j\succ_i j'}x_{ij'}.
\]
Every summand is nonnegative. Therefore no supported partner of \(i\) is strictly worse than \(j\). In particular, \(x_{i,M(i)}>0\) implies that \(i\) does not strictly prefer \(j\) to \(M(i)\).
Likewise, if \(C_{ij}(x)=0\), then \(j\) does not strictly prefer \(i\) to \(M(j)\).
Thus \((i,j)\) cannot block \(M\). This applies to every acceptable pair, proving weak stability. \(\square\)
Conversely, the incidence matrix of any weakly stable perfect matching has \(B=0\): for each acceptable pair, at least one endpoint has no strict improvement, so its corresponding dissatisfaction factor vanishes.
We use the following established theorem: deciding whether an instance of stable marriage with ties and incomplete lists has a weakly stable perfect matching is \(\mathrm{NP}\)-complete. This is Theorem 1 of [Iwama–Manlove–Miyazaki–Morita](https://eprints.gla.ac.uk/1066/1/ICALP99.pdf). Their convention explicitly requires a matching to cover everyone, and their stability definition requires strict improvement at both endpoints.
Take such an instance with \(n\) agents on each side. Compute whether its mutually acceptable graph has a perfect matching.
If it does, create one listed type for each agent, preserve all preferences and acceptable pairs, set every mass to \(1\), and set \(b=0\). Every type is incident to an acceptable pair, and
\[
S^*=n:
\]
an ordinary perfect matching attains \(n\), while total applicant capacity gives the upper bound \(n\).
The equivalence needed for the reduction is now exact:
If the source graph has no perfect matching, the source instance is necessarily a no-instance. Map it to the following fixed no-instance, which satisfies all the task’s promises.
Take
\[
I=\{u,v\},\qquad J=\{p,q\},\qquad
E=\{(u,p),(u,q),(v,p)\},
\]
with all masses equal to \(1\), threshold \(b=0\), and preferences
\[
u:\ p\succ q,\qquad
v:\ p,\qquad
p:\ u\succ v,\qquad
q:\ u.
\]
Here \(S^*=2\). Any assignment attaining \(2\) must saturate every type, so necessarily
\[
x_{uq}=x_{vp}=1,\qquad x_{up}=0.
\]
For the pair \((u,p)\), both dissatisfaction factors equal \(1\). The other products vanish, so \(B(x)=1\). Thus this is a no-instance.
The construction and preliminary matching computation take polynomial time. Therefore the continuous decision problem is \(\mathrm{NP}\)-hard.
We prove a general lemma that supplies both the parameterised algorithm and the rational certificates needed for membership in \(\mathrm{NP}\).
Lemma. Let
\[
P=\{z\in\mathbb R^d:Gz\leq h,\ Hz=k\}
\]
be a nonempty bounded rational polyhedron, with \(r\) inequality rows. Let
\[
q(z)=z^{\mathsf T}Qz+c^{\mathsf T}z+\gamma,
\qquad Q=Q^{\mathsf T},
\]
have rational coefficients. If the total encoding length is \(N\), then:
No convexity assumption is required.
For every subset \(F\subseteq\{1,\ldots,r\}\), form
\[
H_F=
\begin{pmatrix}
H\\G_F
\end{pmatrix},
\qquad
k_F=
\begin{pmatrix}
k\\h_F
\end{pmatrix}.
\]
Compute a rational matrix \(D_F\) whose columns form a basis of \(\ker H_F\).
Using rational linear programming, test feasibility of the linear system
\[
z\in P,\qquad
H_Fz=k_F,\qquad
D_F^{\mathsf T}(2Qz+c)=0.
\]
If feasible, obtain a rational feasible point \(z_F\) and evaluate \(q(z_F)\) exactly. Return the smallest recorded value.
All the displayed constraints are linear in \(z\).
Suppose \(z\) and \(w\) satisfy the system for the same \(F\), and put \(v=w-z\). Their common equality constraints imply
\[
H_Fv=0.
\]
Because \(v\) belongs to the span of the columns of \(D_F\), stationarity at both points gives
\[
v^{\mathsf T}(2Qz+c)=0,
\qquad
v^{\mathsf T}(2Qw+c)=0.
\]
Subtracting yields \(2v^{\mathsf T}Qv=0\). Therefore
\[
q(w)-q(z)
=(2Qz+c)^{\mathsf T}v+v^{\mathsf T}Qv
=0.
\]
Thus any feasible representative has the same objective value as every other point in that candidate set.
Since \(P\) is nonempty and compact, the continuous function \(q\) has a global minimiser \(z^*\).
Let \(F^*\) contain exactly the inequalities tight at \(z^*\). For any \(v\in\ker H_{F^*}\), all equalities and tight inequalities remain equalities along \(z^*+tv\).
Every other inequality has positive slack at \(z^*\). Since there are finitely many inequalities, there exists \(\varepsilon>0\) such that
\[
z^*+tv\in P\qquad\text{whenever }|t|<\varepsilon.
\]
The function \(t\mapsto q(z^*+tv)\) therefore has a local minimum at \(0\), giving
\[
(2Qz^*+c)^{\mathsf T}v=0.
\]
This holds for every \(v\in\ker H_{F^*}\), so
\[
D_{F^*}^{\mathsf T}(2Qz^*+c)=0.
\]
Hence \(z^*\) belongs to the candidate set for \(F^*\). By the preceding calculation, the algorithm’s representative of that set is also a global minimiser.
Every representative considered by the algorithm lies in \(P\). Thus no recorded value is below the global minimum, and at least one equals it. The algorithm is correct.
Rational Gaussian elimination computes each \(D_F\) in polynomial bit complexity, with output encoding length polynomial in \(N\). Consequently, each candidate system has polynomial encoding length.
Exact rational linear programming decides feasibility and returns a polynomial-size rational feasible point in polynomial bit time. There are \(2^r\) subsets \(F\), proving the running-time bound.
For completeness, the existence of a polynomial-size rational representative also follows from boundedness. A nonempty candidate set is a bounded rational polyhedron, so it has a vertex. A vertex is determined by \(d\) linearly independent tight constraints. After clearing denominators, Cramer’s rule expresses its coordinates as ratios of determinants whose encoding lengths are polynomial in \(N\). For \(F^*\), such a vertex is a global minimiser by Section 4.2. \(\square\)
Use one variable per acceptable pair, so the dimension is \(d=|E|\).
First compute \(S^*\) by rational linear programming: maximise the sum of assignments subject to the given capacity and nonnegativity constraints. The feasible region is nonempty because it contains zero, and bounded because every variable is bounded by its incident capacities. Thus \(S^*\) is computable exactly in polynomial bit time and has polynomial encoding length.
The maximum-cardinality feasible region is
\[
P^*=
\left\{
x\in\mathbb R^d:
x\geq0,\
\sum_jx_{ij}\leq\mu_i,\
\sum_ix_{ij}\leq\nu_j,\
\sum_{(i,j)\in E}x_{ij}=S^*
\right\}.
\]
It is nonempty and compact.
There are exactly \(d+\tau\) displayed inequalities: \(d\) nonnegativity constraints and \(\tau\) capacity constraints. The cardinality condition is an equality.
Each \(A_{ij}\) and \(C_{ij}\) is affine with rational coefficients, so \(B\) is a rational quadratic polynomial. Expanding these \(d\) products produces a polynomial-size encoding; symmetrising its quadratic coefficient matrix gives the form required by the lemma.
Apply the lemma to minimise \(B\) over \(P^*\), and compare the exact minimum with \(b\). The resulting bit complexity is
\[
2^{d+\tau}L^{O(1)}.
\]
Since
\[
d\leq |I||J|=m(\tau-m)\leq\frac{\tau^2}{4},
\]
this gives the claimed bounds
\[
2^{m(\tau-m)+\tau}L^{O(1)}
\quad\text{and}\quad
2^{O(\tau^2)}L^{O(1)}.
\]
Hence the problem is FPT parameterised by the number of listed types, without assumptions on mass normalisation, equal side totals, or bounded mass magnitudes.
If an instance is a yes-instance, the minimum of \(B\) over \(P^*\) is at most \(b\). The quadratic-optimisation lemma guarantees a global minimiser with polynomial-size rational coordinates.
Use those coordinates as the certificate. A verifier computes \(S^*\) in polynomial time and checks, using exact rational arithmetic:
These checks take polynomial bit time, so the problem belongs to \(\mathrm{NP}\). Together with Section 3, this proves \(\mathrm{NP}\)-completeness.
The zero-threshold rounding argument establishes hardness for the continuous model itself. The active-constraint algorithm establishes the parameterised bound for arbitrary rational thresholds.
⟨structured verdict parsed — rendered above⟩
The prover resolves the stated continuous decision problem. The NP-hardness reduction, rounding lemma, exact optimisation algorithm, and polynomial-size certificate argument are correct. I found no major or minor mathematical issues.
The established classification is \(\mathrm{NP}\)-complete, with an exact FPT algorithm parameterised by the number \(\tau\) of listed types. The hardness proof uses ties; it does not establish hardness under strict preferences, and the prover does not claim otherwise.
For every feasible assignment, unmatched mass and mass assigned to strictly worse partners are nonnegative. Thus both dissatisfaction factors are nonnegative, including when capacities are not saturated.
Because \(E\) is finite, the sum of these nonnegative products vanishes exactly when every product vanishes. For nonnegative real factors, a product vanishes exactly when at least one factor vanishes. Section 1 therefore establishes its stated equivalence correctly.
Ties are treated correctly: mass assigned to an indifferent partner does not contribute to the strictly-worse-partner sum.
All hypotheses needed by the rounding argument are stated.
For each acceptable pair, at least one endpoint therefore cannot strictly improve. This is exactly weak stability, with ties retained.
The converse is also correct: in the incidence matrix of a perfect matching, each dissatisfaction factor records whether that endpoint strictly prefers the proposed partner to its assigned partner. Weak stability prevents both factors from being positive.
The external theorem is accurately identified and applies as stated. The cited paper’s Theorem 1 establishes NP-completeness for stable marriage with incomplete lists and ties; its definitions require complete coverage and strict improvement at both endpoints. Thus it supplies the precise source problem used here. [Iwama–Manlove–Miyazaki–Morita](https://eprints.gla.ac.uk/1066/1/ICALP99.pdf)
The reduction satisfies the target’s promises:
The branch for source graphs without a perfect matching is legitimate because those source instances cannot possess a weakly stable perfect matching.
The fixed no-instance is correctly computed. At total mass two, saturation forces \(x_{vp}=1\), then \(x_{up}=0\), and then \(x_{uq}=1\). For \((u,p)\), both dissatisfaction factors equal one. For each other acceptable pair, the product is zero. Consequently \(B=1\), so threshold zero is infeasible.
The reduction proves hardness for the continuous problem itself, including the claimed restrictions of unit masses, equal side sizes, a perfect matching in the acceptability graph, and threshold zero.
The lemma’s hypotheses—nonempty, bounded rational polyhedron and rational quadratic objective with symmetric quadratic matrix—are sufficient.
For each inequality subset, the added equalities and stationarity equations are linear with rational coefficients. The candidate system also retains every original constraint, so every representative is feasible for the original optimisation problem.
Dependent equality rows and redundant inequalities cause no problem: the kernel basis remains well defined.
The calculation in Section 4.2 is correct. The difference vector lies in the equality kernel. Stationarity at both points makes its inner product with both gradients vanish. Subtracting gives zero quadratic contribution, and the displayed quadratic expansion then gives equal objective values.
This argument does not require convexity or positive semidefiniteness. Consequently, selecting an arbitrary feasible representative from a candidate system is justified.
Compactness guarantees attainment of the minimum. Selecting exactly the inequalities tight at a minimiser is valid.
For each fixed kernel direction, tight constraints remain equalities, while finitely many strictly slack constraints allow a sufficiently small displacement in both signs. Therefore the directional derivative vanishes. This proves the required stationarity equation for the minimiser.
That candidate system is nonempty, and objective constancy ensures that its chosen representative attains the global minimum. All other representatives remain feasible, so none can have a smaller value.
The stated uses of rational Gaussian elimination and exact rational linear programming are valid for explicitly encoded rational systems. Kernel bases and candidate systems have polynomial encoding length, and each candidate requires polynomial bit time.
The vertex argument also applies to lower-dimensional candidate polyhedra: equalities participate among the active constraints, and a vertex has enough independent active constraint normals to determine its coordinates. Boundedness guarantees a vertex in every nonempty candidate polyhedron.
The determinant argument establishes polynomial-size rational coordinates. Applied to the candidate containing a global minimiser, objective constancy establishes a polynomial-size rational global minimiser.
Thus both conclusions of the lemma follow.
The original feasible assignment region contains zero and is bounded by the positive finite capacities. Exact rational linear programming therefore computes \(S^*\) in polynomial bit time, with polynomial output length.
The maximum-cardinality region is nonempty and compact. Its inequality count is exactly \(d+\tau\); the cardinality requirement is an equality. The objective has a polynomial-size rational quadratic encoding, and symmetrisation preserves it.
The resulting bound is therefore
\[
2^{d+\tau}L^{O(1)}.
\]
Since \(I\) and \(J\) are nonempty and \(|J|=m\), the edge bound
\[
d\leq m(\tau-m)\leq \frac{\tau^2}{4}
\]
is valid. Both advertised bounds follow:
\[
2^{m(\tau-m)+\tau}L^{O(1)}
\quad\text{and}\quad
2^{O(\tau^2)}L^{O(1)}.
\]
The polynomial exponent is independent of the parameter. This establishes FPT for listed types, including arbitrary positive rational masses, unequal side totals, and arbitrary rational thresholds.
The rational-minimiser conclusion supplies a polynomial-size certificate for every yes-instance. Computing \(S^*\), checking feasibility and maximum cardinality, and evaluating the rational quadratic objective all take polynomial bit time. Exact arithmetic handles equality with the threshold without a numerical tolerance assumption.
Together with the reduction, this establishes \(\mathrm{NP}\)-completeness.
No additional clarification or mathematical repair is required.
⟨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.