Answer: \(\mathrm{NP}\)-complete and \(\mathrm{W}[2]\)-hard parameterized by \(k\). It admits an XP algorithm, but no FPT algorithm unless \(\mathrm{FPT}=\mathrm{W}[2]\).
Theorem 6 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximate\exact-\uni-\reor parameterized by~$\ell$ is W[2]-hard, and this also holds if the given matching $\Mst$ is already stable in the original instance and one is only allowed to modify the preferences of agents of one gender.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Input finite male-type and female-type sets \(P\) and \(Q\), rational masses \(\mu^P\) and \(\mu^Q\) of equal total mass, strict rankings of opposite-side types, a target type matching \(\pi\) with \(\mu^P_p=\mu^Q_{\pi(p)}\), and budget \(B\). Choose female types \(S\subseteq Q\), paying \(\sum_{q\in S}\mu^Q_q\), and arbitrarily reorder every member of each selected type. Decide whether the target transport plan \(\nu^\star\), pairing all mass of \(p\) with \(\pi(p)\), is the unique stable transport plan, where stability forbids \(p,q\) with \(\sum_{q'\succ_p q}\nu_{p,q'}>0\) and \(\sum_{p'\succ_q p}\nu_{p',q}>0\).
Input nonempty finite sets of male types \(P\) and female types \(Q\), positive binary rational masses with equal total mass \(T>0\) (not necessarily \(1\)), and strict complete rankings of opposite-side types; \(a\succ_x b\) means that \(x\) prefers \(a\) to \(b\).
A society is given by its support: the list of its \(\tau\) types with positive mass, each with its mass as a binary rational. Here \(m=|P|=|Q|\), \(\tau=|P|+|Q|\) is the support size, not the number of possible types, and \(L\) is the total input bit length.
Also given are a bijection \(\pi:P\to Q\) satisfying \(\mu^P_p=\mu^Q_{\pi(p)}\) and a binary rational budget \(B\geq0\). The target is \(\nu^\star_{p,q}=\mu^P_p\mathbf{1}_{\{q=\pi(p)\}}\).
A transport plan is a nonnegative real matrix \(\nu\) with row sums \(\mu^P\) and column sums \(\mu^Q\). It is stable if no \((p,q)\) satisfies both \(\sum_{q':\,q\succ_p q'}\nu_{p,q'}>0\) and \(\sum_{p':\,p\succ_q p'}\nu_{p',q}>0\).
Choose \(S\subseteq Q\) with \(\sum_{q\in S}\mu^Q_q\leq B\), replacing each selected type's ranking by any one strict complete ranking shared by its entire mass. All other rankings remain fixed.
Decide whether such changes make \(\nu^\star\) the unique stable transport plan. For parameterization, define \(k=\lfloor B/\min_{q\in Q}\mu^Q_q\rfloor\).
Is this decision problem in \(\mathrm{P}\) or \(\mathrm{NP}\)-hard, with running times stated in \(m,\tau,L\)? If it is \(\mathrm{NP}\)-hard, is it FPT parameterized by \(k\), with time \(f(k)(m+\tau+L)^{O(1)}\)?
For finite agents, making a specified matching uniquely stable by reordering preferences is NP-hard and \(\mathrm{W}[2]\)-hard in the number of reordered agents, even with an initially stable target and changes confined to women; an XP algorithm runs in \(O(2^\ell n^{2\ell+2})\). [Source](https://arxiv.org/html/2007.04948)
No result settling this exact transport manipulation problem was located.
The problem is \(\mathrm{NP}\)-complete and is \(\mathrm{W}[2]\)-hard parameterized by \(k\), even when every mass equals \(1\) and the target is initially stable. Consequently, an algorithm running in \(f(k)(m+\tau+L)^{O(1)}\) would imply \(\mathrm{FPT}=\mathrm{W}[2]\).
For arbitrary input masses, there is an XP algorithm. Writing \(K=\min\{k,m\}\), one valid bit-complexity bound is
\(O\!\left(\left(\sum_{r=0}^{K}\binom mr\right)\left[m^2\log(2m)+(\tau+L)^3\right]\right).\)
The key structural result is that, under the paired-mass hypothesis, uniqueness of the target transport is equivalent to uniqueness of the corresponding finite matching. The proof below also gives a polynomial-time algorithm when the set of women whose rankings may change is specified.
Index the types so that \(\pi(p_i)=q_i\), and write \(w_i=\mu^P_{p_i}=\mu^Q_{q_i}>0\). Thus the target transport has entries \(\nu^\star_{i,i}=w_i\), with all other entries zero.
Let \(M=\{(p_i,q_i):1\leq i\leq m\}\) denote the corresponding finite matching.
At the target, the male dissatisfaction in a pair \((p_i,q_j)\) is positive precisely when \(q_j\succ_{p_i}q_i\). The female dissatisfaction is positive precisely when \(p_i\succ_{q_j}p_j\). Positivity of every \(w_i\) is used here. Therefore:
Target-stability equivalence. The transport \(\nu^\star\) is stable if and only if \(M\) is stable as a finite matching.
For the remainder of this section, assume that the target is stable.
Define the male successor \(s_P(i)\) to be the most preferred woman \(q_j\) satisfying
\(q_i\succ_{p_i}q_j\quad\text{and}\quad p_i\succ_{q_j}p_j.\)
If no such woman exists, the successor is undefined. Define the female successor \(s_Q(j)\) symmetrically: it is the most preferred man \(p_i\) satisfying
\(p_j\succ_{q_j}p_i\quad\text{and}\quad q_j\succ_{p_i}q_i.\)
Construct two directed graphs on the indices \(\{1,\ldots,m\}\). The male graph has an arc \(i\to j\) when \(s_P(i)=q_j\); the female graph has an arc \(j\to i\) when \(s_Q(j)=p_i\). Each vertex has at most one outgoing arc.
Proposition. For every choice of positive paired masses \(w_1,\ldots,w_m\), the target transport is uniquely stable if and only if it is stable and both successor graphs are acyclic.
Suppose the male graph contains a cycle \(i_1\to i_2\to\cdots\to i_r\to i_1\). Thus \(s_P(i_a)=q_{i_{a+1}}\), with indices interpreted cyclically.
Choose \(0<\varepsilon<\min_a w_{i_a}\). Starting from \(\nu^\star\), subtract \(\varepsilon\) from each entry \((i_a,i_a)\) and add \(\varepsilon\) to each entry \((i_a,i_{a+1})\). Call the resulting transport \(\widehat\nu\).
Every affected row loses and gains the same amount. Every affected column also loses and gains the same amount. Hence \(\widehat\nu\) is feasible and differs from \(\nu^\star\).
Every woman receives only her target partner and, possibly, a man she prefers to that partner. Every affected man receives his target partner and his male successor, which he likes less.
Suppose a pair \((p_i,q_j)\) could block \(\widehat\nu\). Male dissatisfaction requires \(q_j\) to be preferred to some supported partner of \(p_i\). There are three possible cases:
These cases exhaust the possibilities. Thus \(\widehat\nu\) is stable.
A female successor cycle gives another stable transport by the same construction with the two sides exchanged.
Let \(\nu\neq\nu^\star\) be stable. Define
\(A_P=\{i:\nu_{i,i}<w_i\text{ and every supported partner of }p_i\text{ is weakly preferred to }q_i\},\)
and define \(A_Q\) analogously for women.
At least one of these sets is nonempty. Indeed, choose an off-diagonal positive entry \(\nu_{i,j}>0\).
Suppose first that \(A_P\neq\varnothing\).
If \(i\in A_P\) and \(\nu_{i,j}>0\) with \(j\neq i\), strictness gives \(q_j\succ_{p_i}q_i\). The preceding argument then gives \(j\in A_P\). Thus all mass leaving rows indexed by \(A_P\) enters columns indexed by \(A_P\).
The total mass of these rows and columns is the same, namely \(\sum_{i\in A_P}w_i\). Therefore no positive mass enters those columns from rows outside \(A_P\).
Fix \(j\in A_P\). Since \(\nu_{j,j}<w_j\), there is an off-diagonal supported pair \((p_h,q_j)\). Necessarily \(h\in A_P\), and hence \(q_j\succ_{p_h}q_h\). Target stability gives \(p_j\succ_{q_j}p_h\). Thus \(p_h\) is a candidate for \(s_Q(j)\), so that successor exists.
Write \(s_Q(j)=p_t\). If \(t=h\), then \(t\in A_P\). Otherwise, the choice of the most preferred candidate gives \(p_t\succ_{q_j}p_h\). The supported mass at \((p_h,q_j)\) makes female dissatisfaction at \((p_t,q_j)\) positive. Stability of \(\nu\) therefore forces every supported partner of \(p_t\) to be weakly preferred to \(q_j\). Because \(p_t\) is a successor candidate, \(q_j\succ_{p_t}q_t\). Consequently, every supported partner of \(p_t\) is strictly preferred to his target partner, and \(t\in A_P\).
We have proved that every vertex of the nonempty finite set \(A_P\) has a female-successor arc to another vertex of \(A_P\). Following these arcs must eventually repeat a vertex, producing a directed cycle.
If instead \(A_Q\neq\varnothing\), the identical argument with the sides exchanged produces a cycle in the male successor graph. This proves the proposition.
For completeness, stability is inherited when positive support is reduced: a blocking pair for the smaller support would have a worse supported partner on each side, and those same partners would witness blocking for the larger support.
A successor cycle therefore also produces another stable finite matching: rotate the target partners around the cycle. Its edges are contained in the support of the stable transport constructed in Section 2.1.
Conversely, any stable finite matching different from \(M\) is a stable transport when all paired masses equal \(1\). Section 2.2 then produces a successor cycle.
It follows that, for every fixed preference profile,
\(\nu^\star\text{ is uniquely stable}\quad\Longleftrightarrow\quad M\text{ is the unique stable finite matching}.\)
This statement concerns uniqueness of the specified target; it does not assert that arbitrary stable transports are integral.
A certificate specifies the selected women and their replacement rankings. Its size is polynomial in the input length.
The verifier checks the rational budget, checks target stability, constructs both successor graphs, and tests them for directed cycles. Section 2 proves that this verifies uniqueness among all real-valued feasible transports.
The preference checks take \(O(m^2)\) comparisons after rank preprocessing. Exact rational arithmetic is polynomial in \(L\). Thus the problem belongs to \(\mathrm{NP}\).
Use the women-only restriction of Exact-Unique-Reorder: given a finite stable-marriage instance, a specified complete matching, and budget \(\ell\), decide whether reordering at most \(\ell\) women makes that matching uniquely stable. The cited paper establishes \(\mathrm{NP}\)-hardness and \(\mathrm{W}[2]\)-hardness parameterized by \(\ell\), even with an initially stable target. [Boehmer, Bredereck, Heeger, and Niedermeier, Theorem 6](https://arxiv.org/html/2007.04948#S5.SS1)
Create one type per agent, preserve the rankings and target bijection, give every type mass \(1\), and set \(B=\ell\). Then \(T=m\), \(\tau=2m\), and \(k=\ell\).
Selecting women has exactly the original cardinality cost. By Section 2.3, every modified profile makes the target finite matching uniquely stable if and only if it makes the target transport uniquely stable.
The construction has polynomial size and preserves the parameter. Hence the transport problem is \(\mathrm{NP}\)-hard and \(\mathrm{W}[2]\)-hard parameterized by \(k\). Together with membership, this proves \(\mathrm{NP}\)-completeness.
Fix a set \(S\subseteq Q\) whose rankings may be replaced. We now decide in polynomial time whether some replacements succeed.
First reject if the target has a blocking pair involving a woman outside \(S\). Such a pair cannot be removed because both relevant rankings remain fixed.
Introduce a sink vertex \(t\). Construct two graphs of allowed successors on \(\{1,\ldots,m\}\cup\{t\}\).
For each woman \(q_j\), let
\(C_j=\{i:q_j\succ_{p_i}q_i\}.\)
These are exactly the men who prefer her to their target partners.
If \(q_j\in S\), target stability requires her to place her own partner above every member of \(C_j\). Therefore:
Each candidate can be made her female successor by placing it immediately after her own partner.
If \(q_j\notin S\), her successor is fixed. Add its arc, or add \(j\to t\) if it is undefined. Call this graph \(H_Q\).
For each man \(p_i\), let \(b_i\) be his most preferred unselected woman satisfying
\(q_i\succ_{p_i}b_i\quad\text{and}\quad p_i\succ_{b_i}\pi^{-1}(b_i).\)
If no such woman exists, set \(b_i=t\). Add the corresponding fixed arc from \(i\).
For every selected woman \(q_j\), also add \(i\to j\) when
\(q_i\succ_{p_i}q_j\)
and either \(b_i=t\) or \(q_j\succ_{p_i}b_i\).
These are exactly the selected women who can become his first successor before the earliest fixed candidate. Call this graph \(H_P\).
In a graph of allowed successors, one can choose one outgoing arc per non-sink vertex and obtain an acyclic graph if and only if every vertex can reach \(t\).
For necessity, following chosen arcs in a finite acyclic graph must terminate at the only vertex without a chosen outgoing arc, namely \(t\). For sufficiency, choose an arc that decreases shortest-path distance to \(t\).
Therefore the fixed-set algorithm accepts exactly when every vertex reaches \(t\) in both \(H_P\) and \(H_Q\).
To prove that the two choices can be realized simultaneously, choose acyclic outgoing arcs in both graphs. For each selected woman \(q_j\), replace her ranking as follows:
Every man placed above \(p_j\) prefers his own target partner to \(q_j\), by the definition of \(H_P\). Thus these placements cannot block the target. A chosen female successor belongs to \(C_j\), so it cannot conflict with an above-partner placement.
The resulting female successors are exactly the chosen ones. The male successors are also exactly the chosen ones: each man is placed above the target partner of at most his chosen selected successor, and that successor precedes every fixed candidate.
Both actual successor graphs are therefore acyclic, and Section 2 proves uniqueness.
Conversely, any successful replacements supply actual successor arcs contained in \(H_P\) and \(H_Q\). Their acyclicity implies the required reachability. This proves correctness.
Both graphs have \(O(m^2)\) arcs and can be constructed and checked in polynomial time.
Every affordable selection satisfies
\(|S|\min_{q\in Q}\mu^Q_q\leq\sum_{q\in S}\mu^Q_q\leq B,\)
so \(|S|\leq k\).
Enumerate all subsets of at most \(K=\min\{k,m\}\) women, discard those exceeding the rational budget, and apply Section 4 to each remaining subset.
A conservative bit-complexity bound is
\(O\!\left(\left(\sum_{r=0}^{K}\binom mr\right)\left[m^2\log(2m)+(\tau+L)^3\right]\right).\)
Here the cubic term permits straightforward exact arithmetic on the binary rational input. In particular, this is bounded by
\(O\!\left((K+1)m^K\left[m^2\log(2m)+(\tau+L)^3\right]\right),\)
and unrestricted enumeration gives \(2^m(m+\tau+L)^{O(1)}\) time. Recall that this problem has \(\tau=2m\).
Thus the problem is in XP parameterized by \(k\). Its \(\mathrm{W}[2]\)-hardness rules out an FPT algorithm under the standard assumption \(\mathrm{FPT}\neq\mathrm{W}[2]\); an unconditional separation is not claimed.
⟨structured verdict parsed — rendered above⟩
The prover’s argument resolves the task. The structural equivalence, hardness reduction, and fixed-set algorithm are correct as written. I found no major or minor mathematical gaps.
At the target, each type has exactly one supported partner, with positive mass. Consequently, male dissatisfaction at \((p_i,q_j)\) is positive exactly when \(q_j\succ_{p_i}q_i\), and female dissatisfaction is positive exactly when \(p_i\succ_{q_j}p_j\).
These are precisely the finite matching’s blocking conditions. The equivalence is valid for arbitrary positive paired masses and requires no normalization of total mass.
The construction in Section 2.1 is valid.
The blocking-pair analysis is exhaustive. For an affected man, a woman preferred to some supported partner must be either above his target partner, his target partner, or strictly between his target partner and his successor. The successor itself cannot create male dissatisfaction: his two supported partners are his target partner and that successor.
In the third case, the definition of the most preferred successor excludes a woman who prefers this man to her target partner. In all three cases, female dissatisfaction is zero.
The argument with the sexes exchanged is valid. Thus either successor cycle witnesses nonuniqueness.
Section 2.2 correctly treats arbitrary real-valued transports.
Because the row margins equal the target diagonal entries, any transport different from the target has positive off-diagonal mass. Strict rankings give the two cases considered by the prover. Target stability and stability of the alternative transport imply that at least one of \(A_P\) and \(A_Q\) is nonempty.
For \(A_P\), the subsequent steps are valid:
Thus the female-successor function maps the nonempty finite set \(A_P\) into itself, producing a directed cycle. The symmetric argument applies to \(A_Q\).
No integrality assumption is used. This establishes the claimed characterization of uniqueness among all feasible real transports.
The support argument in Section 2.3 is sound: any blocking witnesses in a reduced positive support remain blocking witnesses in the original support.
Rotating partners around a successor cycle gives a complete finite matching whose support is contained in the constructed stable transport’s support. It is therefore stable and differs from the target matching.
Conversely, with unit masses, every complete stable finite matching is a feasible stable transport. Applying Section 2.2 yields a successor cycle.
Together with target-stability equivalence, these implications establish the claimed equivalence for every fixed preference profile. They do not require alternative finite matchings to satisfy the original unequal margins.
The certificate consists of a selected subset and strict replacement rankings, so its size is polynomial. Budget checking uses exact rational arithmetic. Target stability, successor construction, and cycle detection are polynomial-time operations.
The external hardness claim is supported by [Theorem 6 of the cited paper](https://arxiv.org/html/2007.04948#S5.SS1). It establishes parameterized hardness even with an initially stable target and modifications confined to one gender; its construction uses women-only modifications and a polynomial-size reduction from Hitting Set, supporting ordinary NP-hardness as well.
The transport reduction satisfies every required hypothesis:
Selection cost is exactly the number of reordered women. The established uniqueness equivalence supplies both directions of the reduction for every modified profile.
Therefore the NP-completeness and parameterized \(\mathrm{W}[2]\)-hardness conclusions follow.
The initial rejection condition is necessary: a blocking pair involving an unselected woman has both relevant rankings fixed.
The allowed-successor graphs are characterized correctly.
For a selected woman, target stability forces every member of \(C_j\) below her target partner. If \(C_j\) is nonempty, its highest-ranked member is her female successor, and any member can occupy that position. If it is empty, her successor is undefined.
For each man, the earliest unselected successor candidate is fixed. A selected woman can become his successor precisely when she is below his target partner and precedes that fixed candidate, if one exists.
The reachability criterion is valid because every ordinary vertex receives exactly one chosen outgoing arc, while the sink receives none.
The simultaneous realization argument also holds:
Consequently, both actual successor graphs equal the chosen acyclic graphs. Conversely, any successful replacement profile supplies allowed acyclic successor choices and therefore the required reachability.
Every affordable subset has size at most \(k\), so enumerating subsets of size at most \(K=\min\{k,m\}\) is sufficient.
Each fixed-set check uses graphs with \(O(m^2)\) arcs. The stated \(m^2\log(2m)\) term accommodates rank processing, and the cubic term conservatively accommodates straightforward exact rational arithmetic: intermediate numerator and denominator lengths remain polynomially bounded by the total input length.
The subset-count bound, XP conclusion, and unrestricted exponential-time bound are valid. The argument also covers zero budget, an empty selected set, one type per side, unequal paired masses, and budgets large enough to permit every woman.
The FPT exclusion is correctly conditional on \(\mathrm{FPT}\neq\mathrm{W}[2]\). No additional clarification or 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.