Answer: \(\mathrm{NP\text{-}complete}\); it is \(\mathrm{W[1]}\)-hard parameterized by \(|H|\) and belongs to \(\mathrm{XP}\), so it is not fixed-parameter tractable unless \(\mathrm{FPT}=\mathrm{W[1]}\).
Theorem 3 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateParameterized by the number m of hospi- tals, IHR-T is W[1]-hard even if |P1 ⊕P2| = 1.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given resident types \Theta_R with rational masses \mu_\theta, hospitals \(H\) with capacities \(q_h\), type-level old and new profiles \(P_1,P_2\), a \(P_1\)-stable initial flow \(x^1\), and rational \kappa, decide whether a feasible \(P_2\)-stable flow \(x\) satisfies \sum_{\theta,h}\lvert x_{\theta h}-x^1_{\theta h}\rvert\le\kappa; stability requires \(r_{\theta h}(x)s_{h\theta}(x)=0\) for every acceptable pair, where \(r_{\theta h}\) is mass preferring \(h\) to its assignment and \(s_{h\theta}\) is capacity not occupied by residents ranked at least as highly as \theta. The new profile may differ by one adjacent swap in one positive-mass resident type.
Let \(\Theta_R\) be resident types with rational masses \(\mu_\theta\), and let hospitals \(H\) have rational capacities \(q_h\). In each profile, resident types and hospitals have preference orders, possibly with ties, over mutually acceptable counterparts; being unmatched is worse than every acceptable hospital. A flow \(x\) is feasible if \(x_{\theta h}\ge 0\), \(\sum_h x_{\theta h}\le\mu_\theta\), and \(\sum_\theta x_{\theta h}\le q_h\).
For an acceptable pair \((\theta,h)\), set \(r_{\theta h}(x)=\mu_\theta-\sum_gx_{\theta g}+\sum_{g:\,h\succ_\theta g}x_{\theta g}\) and \(s_{h\theta}(x)=q_h-\sum_{\theta':\,\theta'\succeq_h\theta}x_{\theta'h}\). A feasible flow is stable when \(r_{\theta h}(x)s_{h\theta}(x)=0\) for every acceptable pair.
Given profiles \(P_1,P_2\), a \(P_1\)-stable flow \(x^1\), and rational \(\kappa\), where \(P_2\) is obtained from \(P_1\) by one adjacent swap in one positive-mass resident type's preference list, decide whether a feasible \(P_2\)-stable flow \(x\) satisfies \(\sum_{\theta,h}|x_{\theta h}-x^1_{\theta h}|\le\kappa\).
Target. Is this continuous incremental stable-flow problem solvable in polynomial time, or is it NP-hard? If it is NP-hard, is it fixed-parameter tractable when parameterized by \(|H|\)?
Nearest known results. The finite-agent Hospital Residents problem with ties is NP-hard and W[1]-hard parameterized by the change budget, even for one adjacent swap. It is also W[1]-hard parameterized by the number of hospitals for one adjacent swap, while it is in XP for that parameter.
No verified complexity classification was found for this exact distribution-over-types flow formulation.
Using the finite-agent hardness results stated in the question, the continuous incremental stable-flow problem is \(\mathrm{NP}\)-complete, even when every resident type has mass \(1\), all hospital capacities are integral, the given flow \(x^1\) is integral, and \(P_2\) differs from \(P_1\) by one adjacent swap.
Parameterized by \(|H|\), the problem is \(\mathrm{W[1]}\)-hard and belongs to \(\mathrm{XP}\). Consequently, it is not fixed-parameter tractable unless \(\mathrm{FPT}=\mathrm{W[1]}\).
The essential point is that fractional flows cannot create false positive instances in the integral-mass restriction.
Let \(E\) denote the set of mutually acceptable pairs. Write
\(\deg_\theta(x)=\sum_h x_{\theta h}\)
and
\(\deg_h(x)=\sum_\theta x_{\theta h}\).
For every acceptable pair \((\theta,h)\),
\(r_{\theta h}(x)=\bigl(\mu_\theta-\deg_\theta(x)\bigr)+\sum_{g:\,h\succ_\theta g}x_{\theta g}\).
Because the hospital preference relation is a total preorder on its acceptable resident types,
\(s_{h\theta}(x)=\bigl(q_h-\deg_h(x)\bigr)+\sum_{\theta':\,\theta\succ_h\theta'}x_{\theta'h}\).
Every summand in both expressions is nonnegative. Consequently,
\(r_{\theta h}(x)=0\)
holds exactly when type \(\theta\) is fully assigned and no positive mass of \(\theta\) is assigned to a hospital strictly worse than \(h\). Similarly,
\(s_{h\theta}(x)=0\)
holds exactly when \(h\) is full and assigns no positive mass to a type strictly worse than \(\theta\).
Thus the stability condition says that for every acceptable pair, at least one of these two saturation properties holds.
Consider the restricted case \(\mu_\theta=1\) for every type and \(q_h\in\mathbb Z_{\geq 0}\). Let \(M\) be an integral feasible flow. Then every \(M_{\theta h}\) belongs to \(\{0,1\}\), so \(M\) is an ordinary hospital–resident matching.
For an acceptable pair \((\theta,h)\), the inequality \(r_{\theta h}(M)>0\) holds precisely when \(\theta\) is unmatched or is assigned to a hospital strictly worse than \(h\).
Likewise, \(s_{h\theta}(M)>0\) holds precisely when either \(h\) has a vacancy or \(h\) is full but contains a resident type strictly worse than \(\theta\).
Therefore \(r_{\theta h}(M)s_{h\theta}(M)>0\) holds exactly when \((\theta,h)\) is a blocking pair under the usual weak-stability convention for preferences with ties. Hence integral stable flows are exactly weakly stable hospital–resident matchings.
Suppose \(\mu_\theta=1\) for every resident type and every \(q_h\) is integral. Every stable flow \(x\) is a convex combination of integral stable matchings.
Consider the bipartite \(b\)-matching polytope
\(\mathcal B=\{x\geq 0:\deg_\theta(x)\leq 1\text{ for every }\theta,\ \deg_h(x)\leq q_h\text{ for every }h\}\).
The constraint matrix is the vertex-edge incidence matrix of a bipartite graph and is totally unimodular. Its right-hand side is integral. Since \(\mathcal B\) is bounded, every \(x\in\mathcal B\) admits a decomposition
\(x=\sum_{i=1}^t\lambda_iM^i\),
where \(\lambda_i>0\), \(\sum_i\lambda_i=1\), and every \(M^i\) is an integral feasible matching.
Fix an acceptable pair \((\theta,h)\). Stability of \(x\) gives either \(r_{\theta h}(x)=0\) or \(s_{h\theta}(x)=0\).
Suppose first that \(r_{\theta h}(x)=0\). By the nonnegative-sum expression above,
\(\deg_\theta(x)=1\)
and
\(x_{\theta g}=0\)
for every \(g\) satisfying \(h\succ_\theta g\).
Since every \(\deg_\theta(M^i)\leq1\) and their weighted average is \(1\), necessarily \(\deg_\theta(M^i)=1\) for every \(i\). Moreover, a nonnegative coordinate whose weighted average is zero is zero in every positively weighted component. Thus \(M^i_{\theta g}=0\) for every \(g\) strictly worse than \(h\). Hence \(r_{\theta h}(M^i)=0\) for every \(i\).
Suppose instead that \(s_{h\theta}(x)=0\). Then
\(\deg_h(x)=q_h\)
and
\(x_{\theta'h}=0\)
for every \(\theta'\) satisfying \(\theta\succ_h\theta'\).
Since every \(\deg_h(M^i)\leq q_h\) and their weighted average is \(q_h\), every \(M^i\) fills \(h\). Again, every coordinate corresponding to a type strictly worse than \(\theta\) is zero in every component. Therefore \(s_{h\theta}(M^i)=0\) for every \(i\).
This argument applies simultaneously to every acceptable pair. Thus every \(M^i\) is stable. ∎
Let \(x^1\) be an integral matching. For every feasible \(y\), each coordinate satisfies \(0\leq y_e\leq1\). Therefore
\(\|y-x^1\|_1=\sum_{e:\,x^1_e=0}y_e+\sum_{e:\,x^1_e=1}(1-y_e)\).
Thus the distance from \(x^1\) is affine on the entire feasible-flow polytope.
Applying this identity to the decomposition from the lemma gives
\(\|x-x^1\|_1=\sum_i\lambda_i\|M^i-x^1\|_1\).
Consequently, at least one component \(M^i\) satisfies
\(\|M^i-x^1\|_1\leq\|x-x^1\|_1\).
We have therefore proved the exact equivalence:
There exists a stable fractional flow \(x\) with \(\|x-x^1\|_1\leq\kappa\) if and only if there exists an integral stable matching \(M\) with \(\|M-x^1\|_1\leq\kappa\).
For integral matchings, this \(\ell_1\) distance is exactly the edge-symmetric-difference distance \(|M\mathbin{\triangle}M^1|\).
Take an instance of finite Incremental Hospital Residents with ties from the hardness result supplied in the question.
For every finite resident \(v\), introduce a separate resident type \(\theta_v\) of mass \(1\). Keep the hospitals, their integral capacities, acceptability relation, and all preference orders unchanged, replacing each resident \(v\) in a hospital preference list by \(\theta_v\). Let \(x^1\) be the incidence vector of the given matching \(M^1\), and retain the same budget \(\kappa\).
This construction is polynomial. It also preserves:
The equivalence proved above shows that the continuous instance is a yes-instance exactly when the finite instance is a yes-instance. Hence the continuous problem is \(\mathrm{NP}\)-hard. The parameter-preserving version of the same reduction transfers \(\mathrm{W[1]}\)-hardness parameterized by \(|H|\).
For every acceptable pair \((\theta,h)\), nondeterministically choose one of the two linear equalities
\(r_{\theta h}(x)=0\)
or
\(s_{h\theta}(x)=0\).
After these choices, impose feasibility together with auxiliary variables \(d_{\theta h}\) satisfying
\(d_{\theta h}\geq x_{\theta h}-x^1_{\theta h}\),
\(d_{\theta h}\geq x^1_{\theta h}-x_{\theta h}\),
and
\(\sum_{\theta,h}d_{\theta h}\leq\kappa\).
This is a rational linear system of polynomial size. If a stable real solution exists, choosing one vanishing factor for every pair produces a nonempty rational polyhedron. Standard determinant bounds for rational linear systems imply that this polyhedron contains a rational point of polynomial encoding length. Such a point, together with the choices of vanishing factors, is a polynomial certificate.
Conversely, every solution of one of these systems is stable because every acceptable pair has at least one zero residual. Thus the problem belongs to \(\mathrm{NP}\), and the preceding hardness result makes it \(\mathrm{NP}\)-complete.
For a hospital \(h\), define
\(Z_h(x)=\{\theta:(\theta,h)\in E\text{ and }s_{h\theta}(x)=0\}\).
If \(\theta\in Z_h(x)\) and \(h\) weakly prefers \(\theta\) to \(\theta''\), then the upper contour of \(\theta''\) contains the upper contour of \(\theta\). Since the latter already carries mass \(q_h\), feasibility implies that the former also carries exactly \(q_h\). Hence \(\theta''\in Z_h(x)\).
Therefore \(Z_h(x)\) is a suffix of the tie classes in \(h\)'s preference order. If there are \(\ell_h\) tie classes, there are only \(\ell_h+1\) possible suffixes, including the empty suffix.
Enumerate one suffix \(Z_h\) for every hospital. For a fixed tuple of suffixes, solve the rational linear program consisting of feasibility, the distance constraint, and
\(s_{h\theta}(x)=0\) for \(\theta\in Z_h\),
\(r_{\theta h}(x)=0\) for \(\theta\notin Z_h\).
Every solution of such a linear program is stable. Conversely, every stable flow is captured by choosing its actual sets \(Z_h(x)\), because whenever \(s_{h\theta}(x)>0\), stability forces \(r_{\theta h}(x)=0\).
Writing \(n=|\Theta_R|\) and \(m=|H|\), the number of tuples is at most \((n+1)^m\). Each associated linear program has polynomial size. The running time is therefore
\((|\Theta_R|+1)^{|H|}\operatorname{poly}(|I|)\),
which places the problem in \(\mathrm{XP}\) parameterized by \(|H|\).
Divisibility does not eliminate the finite-agent hardness: on unit masses and integral capacities, every stable fractional witness can be rounded to a stable integral witness without increasing its distance from the given matching. The problem is therefore \(\mathrm{NP}\)-complete and \(\mathrm{W[1]}\)-hard parameterized by the number of hospitals. It has an \(\mathrm{XP}\) cutoff-enumeration algorithm, but an \(\mathrm{FPT}\) algorithm would imply \(\mathrm{FPT}=\mathrm{W[1]}\).
⟨structured verdict parsed — rendered above⟩
The argument is mathematically sound under two additional assumptions that are not established in the write-up:
Under the literal formulation of USER_TASK, the first assumption is false: feasibility does not require \(x_{\theta h}=0\) for unacceptable pairs. This invalidates a central correspondence used by the reduction. Consequently, the claimed NP-hardness and W[1]-hardness are not verified as written.
The expression for \(r_{\theta h}(x)\) is correct.
The claimed expression
\[ s_{h\theta}(x)=\bigl(q_h-\deg_h(x)\bigr)+\sum_{\theta':\,\theta\succ_h\theta'}x_{\theta'h} \]
is valid only if \(x_{\theta'h}=0\) whenever \((\theta',h)\) is unacceptable. Otherwise \(\deg_h(x)\) includes mass from types absent from \(h\)'s preference order, while neither term in the defining upper-contour sum accounts for that mass.
For example, let \(q_h=1\), let \(h\) find \(\theta\) acceptable but \(\theta'\) unacceptable, and take \(x_{\theta'h}=1\), \(x_{\theta h}=0\). Then the definition gives \(s_{h\theta}(x)=1\), while the displayed alternative expression gives \(0\).
Thus the nonnegative-summand characterization of \(s_{h\theta}(x)=0\) is not established for the stated feasible-flow domain.
The statement that every integral feasible flow is an ordinary hospital–resident matching is false under the literal feasibility definition.
A minimal failure is:
This is feasible. For the only acceptable pair \((\theta,h)\),
\[ r_{\theta h}(x)=1-1+0=0, \]
so the flow satisfies stability regardless of \(s_{h\theta}(x)\). But assigning \(\theta\) to \(g\) is not an ordinary hospital–resident matching. Hence integral stable flows do not coincide with weakly stable finite matchings unless acceptable support is imposed.
Conditional on acceptable support, the comparison between positive residuals and weak blocking pairs is correct.
Conditional on the flow vector being indexed only by acceptable edges, the lemma is correct:
Without acceptable support, the integral components may use unacceptable edges and therefore are not finite hospital–resident matchings. The lemma then does not provide the property needed by the reduction.
Conditional on the preceding lemma, this part is correct. Because \(x^1_e\in\{0,1\}\) and \(0\leq y_e\leq1\), the distance from \(x^1\) is affine, and at least one component has distance no greater than the convex average.
The identification with edge-symmetric-difference distance is also correct for integral incidence vectors.
The reduction is not verified for two independent reasons.
First, unacceptable coordinates remain available in the constructed continuous instance under the stated feasibility definition. Such coordinates can produce stable flows that do not represent finite matchings, so the claimed yes-instance equivalence does not follow.
Second, the invoked finite theorem is not stated precisely enough. The proof needs the finite problem's budget to be exactly \(|M\mathbin{\triangle}M^1|\). If “change budget” instead counts residents whose assignments change, retaining the same \(\kappa\) is not valid: changing from one hospital to another contributes two edges to symmetric difference, whereas changing between matched and unmatched contributes one. The write-up also does not verify that the source hardness theorem places its adjacent swap specifically in a resident's preference list, as required by the target.
These are hypotheses of the reduction, not merely bibliographic details.
This section is correct. Guessing one zero factor per acceptable pair yields a polynomial-size rational linear system. The auxiliary inequalities correctly encode the existence of distances satisfying the \(\ell_1\) budget, and a nonempty rational polyhedron has a rational feasible point of polynomial encoding length by standard basic-solution bounds.
The suffix property of \(Z_h(x)\) follows directly from nesting of hospital upper contours and feasibility. The enumeration contains every stable flow, and every solution to an enumerated linear program is stable.
The bound \((|\Theta_R|+1)^{|H|}\operatorname{poly}(|I|)\) correctly establishes XP membership parameterized by \(|H|\). This remains genuine progress, but XP membership alone does not settle whether the problem is polynomial-time solvable or NP-hard.
The write-up needs:
⟨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.