Answer: \(\mathrm{NP}\text{-hard}\)
Theorem 2 — class: hardness
Given finite applicant and position category sets \(I\) and \(J\), rational distributions over applicant types \(t=(i,j_0,\pi)\) and position types \(u=(j,i_0,\rho)\), and a stable incumbent mass coupling \(\kappa\) with those marginals supported only where \(j=j_0\) and \(i=i_0\), may the preference rankings be changed so that the blocking-pair density reaches \(\beta\) within swap budget \(\varepsilon\)? An edit transfers mass only between types with the same own category and incumbent partner category; its cost is transferred mass times Kendall swap distance between rankings, summed over both sides. For edited distributions \(\nu,\omega\), the blocking-pair density is \(B(\nu,\omega)=\sum_{t,u}\nu_t\omega_u\,\mathbf{1}[\operatorname{rk}_{\pi_t}(j)<\operatorname{rk}_{\pi_t}(j_0)\ \wedge\ \operatorname{rk}_{\rho_u}(i)<\operatorname{rk}_{\rho_u}(i_0)]\); the decision question is whether feasible edits of total cost at most \(\varepsilon\) yield \(B(\nu,\omega)\ge\beta\).
Let \(I,J\) be nonempty finite category sets and \(m=|I|+|J|\). Applicant types are \(t=(i,j_0,\pi)\), where \(i\in I\), \(j_0\in J\), and \(\pi\) is a strict complete ranking of \(J\); position types are \(u=(j,i_0,\rho)\), defined symmetrically with rankings of \(I\).
Each side's society is given by its support: the list of types with positive mass, each mass a binary rational. Initial distributions \(\mu,\eta\) each have total mass \(1\); \(\tau\) is their combined support size, not the number of possible types. Let \(L\) be the total input bit length.
The input also gives a rational incumbent coupling \(\kappa\), listed by its positive entries, with marginals \(\mu,\eta\), supported only on pairs satisfying \(j=j_0\) and \(i=i_0\). All mass is matched, and incumbent partners remain fixed throughout editing.
For any distributions \(\nu,\omega\), define \(B(\nu,\omega)=\sum_{t=(i,j_0,\pi),\,u=(j,i_0,\rho)}\nu_t\omega_u\mathbf{1}[\operatorname{rk}_{\pi}(j)<\operatorname{rk}_{\pi}(j_0)\ \land\ \operatorname{rk}_{\rho}(i)<\operatorname{rk}_{\rho}(i_0)]\). The initial incumbent is stable: \(B(\mu,\eta)=0\).
An edit consists of nonnegative real transport plans \(P,Q\) with marginals \((\mu,\nu)\) and \((\eta,\omega)\). Transport preserves \((i,j_0)\) on the applicant side and \((j,i_0)\) on the position side; mass may split among any strict complete rankings, including rankings absent from the input support.
Its cost is \(C(P,Q)=\sum_{t,t'}P_{tt'}d_K(\pi_t,\pi_{t'})+\sum_{u,u'}Q_{uu'}d_K(\rho_u,\rho_{u'})\), where \(d_K\) is the unnormalized Kendall swap distance. Given binary rational \(\varepsilon\ge0\) and \(\beta\in[0,1]\), decide whether edits exist with \(C(P,Q)\le\varepsilon\) and \(B(\nu,\omega)\ge\beta\).
Is this continuous blocking-pair-density decision problem in \(\mathrm{P}\), with running time polynomial in \(m,\tau,L\), or is it \(\mathrm{NP}\)-hard?
The discrete problem of creating at least a specified number of blocking pairs for a fixed matching within an adjacent-swap budget is NP-complete. [Verified discrete result](https://arxiv.org/pdf/2408.09160).
No result settling this exact continuous transport-and-density problem was found in the literature search.
The continuous decision problem is \(\mathrm{NP}\)-hard under polynomial-time many-one reductions. The proof allows arbitrary real transports, mass splitting, and rankings absent from the input support.
We reduce from Balanced Biclique: given a bipartite graph \(G=(V,W,E)\) and an integer \(k\), decide whether there are subsets \(S\subseteq V\), \(T\subseteq W\) with \(|S|=|T|=k\) and \(S\times T\subseteq E\). This problem is \(\mathrm{NP}\)-complete; see the introduction of [Peeters, *The maximum edge biclique problem is NP-complete*](https://cgi.di.uoa.gr/~vassilis/co/biclique.pdf). We restrict to \(1\le k\le\min\{|V|,|W|\}\), since instances outside this range are trivial.
The key is a quantitative gap that remains valid for fractional choices.
For vectors \(x\in[0,1]^V\) and \(y\in[0,1]^W\), define
\(F_G(x,y)=\sum_{(v,w)\in E}x_vy_w.\)
Lemma 1. If \(G\) contains no balanced biclique of size \(k\), then
\(\sum_vx_v+\sum_wy_w\le 2k\quad\Longrightarrow\quad F_G(x,y)\le k^2-\tfrac14.\)
Proof. Put \(a=\sum_vx_v\) and \(b=\sum_wy_w\).
If \(|a-k|\ge\tfrac12\), nonnegativity and \(a+b\le2k\) give
\(F_G(x,y)\le ab\le a(2k-a)=k^2-(a-k)^2\le k^2-\tfrac14.\)
The same calculation applies with \(b\) in place of \(a\) if \(|b-k|\ge\tfrac12\).
It remains to consider
\(k-\tfrac12<a<k+\tfrac12,\qquad k-\tfrac12<b<k+\tfrac12.\)
Fix these sums. Holding \(y\) fixed, maximize the linear function \(F_G(\,\cdot\,,y)\) over
\(P_a=\{z\in[0,1]^V:\sum_vz_v=a\}.\)
This nonempty bounded polytope has an extreme-point maximizer \(x^*\). Every extreme point of \(P_a\) has at most one coordinate strictly between zero and one: if two coordinates were fractional, small opposite perturbations of them would preserve the sum and express the point as the midpoint of two distinct feasible points.
Holding \(x^*\) fixed, similarly choose an extreme-point maximizer \(y^*\) with sum \(b\). Thus
\(F_G(x,y)\le F_G(x^*,y^*).\)
An extreme point with sum in \((k-\tfrac12,k+\tfrac12)\) has at least \(k\) coordinates at least \(\tfrac12\). Indeed, it either has at least \(k\) coordinates equal to one, or has \(k-1\) such coordinates and one fractional coordinate greater than \(\tfrac12\).
Choose \(k\) such coordinates on each side. Since they do not form a biclique, some pair \((v,w)\) among them is absent from \(E\). Consequently,
\(F_G(x^*,y^*)=ab-\sum_{(v,w)\in(V\times W)\setminus E}x_v^*y_w^*\le ab-\tfrac14\le k^2-\tfrac14,\)
where the last inequality follows from \(a+b\le2k\). This proves the lemma. \(\square\)
Lemma 2. Suppose an initial ranking places the incumbent category first and a target category in position \(r\). Every ranking that places the target above the incumbent has Kendall distance at least \(r-1\) from the initial ranking.
Proof. The incumbent–target comparison must reverse. For each of the \(r-2\) categories initially between them, at least one of its comparisons with these two categories must also reverse; otherwise the target could not precede the incumbent.
These are at least \(r-1\) distinct reversed comparisons. Each adjacent swap changes only one unordered comparison, so at least \(r-1\) swaps are necessary. \(\square\)
This bound applies to every destination ranking separately, hence also to arbitrary split transport plans.
Let \(n=|V|+|W|\). Let \(N\) be the smallest power of two satisfying \(N\ge n+1\), and set
\(h=N^{-1},\qquad D=64nk^2,\qquad H=64k(D+n)N.\)
All these parameters have polynomial magnitude in \(n\).
Introduce applicant categories
\(I=\{a_v:v\in V\}\cup\{c_w:w\in W\}\cup\{a_*\}\cup\{z_1^I,\ldots,z_H^I\},\)
and position categories
\(J=\{d_v:v\in V\}\cup\{b_w:w\in W\}\cup\{b_*\}\cup\{z_1^J,\ldots,z_H^J\}.\)
All labels within a side are distinct. The categories \(z_\ell^I,z_\ell^J\) carry no mass. This is permitted by the stated hypotheses. Transport preserves an agent’s own category, so these categories remain without mass throughout editing.
There is exactly one initial ranking for each of the following supported identities:
| Index | Applicant identity \((i,j_0)\) | Position identity \((j,i_0)\) | Mass on each side |
|---|---|---|---|
| \(v\in V\) | \((a_v,d_v)\) | \((d_v,a_v)\) | \(h\) |
| \(w\in W\) | \((c_w,b_w)\) | \((b_w,c_w)\) | \(h\) |
| Auxiliary pair | \((a_*,b_*)\) | \((b_*,a_*)\) | \(1-nh\) |
The last mass is positive because \(N\ge n+1\). Both societies have total mass one.
The incumbent coupling matches the two types in each row, with the indicated mass. It therefore has the required marginals and satisfies \(j=j_0\) and \(i=i_0\).
Call applicants of category \(a_v\) and positions of category \(b_w\) active. All other supported agents are inactive.
For active applicant \(a_v\), concatenate the following blocks:
For active position \(b_w\), use the symmetric ranking:
Every inactive agent ranks its incumbent first, then all \(H\) barrier categories, then all remaining categories.
These are strict complete rankings. Everyone initially ranks their incumbent first, so \(B(\mu,\eta)=0\).
Set
\(\varepsilon=2kh(D+n),\qquad \beta=h^2k^2.\)
Both numbers, and all input masses, are dyadic rationals. Also \(0<\beta<1\), since \(k\le n/2<N\).
The combined support size is \(\tau=2(n+1)\), and
\(m=2(n+1+H).\)
Because \(k\le n\) and \(N<2(n+1)\), we have \(H=O(n^5)\). There are \(2(n+1)\) complete rankings, each of polynomial length, and \(n+1\) positive coupling entries. Thus the construction and its total bit length are polynomial in the source input size.
Suppose \(S\subseteq V\) and \(T\subseteq W\) form a balanced biclique of size \(k\).
For every \(v\in S\), edit its entire applicant mass by moving its incumbent downward past the first \(D\) barrier categories and all its graph neighbors. This costs exactly \(D+\deg_G(v)\) swaps per unit mass.
Perform the symmetric edit for every active position indexed by \(w\in T\). Leave every other ranking unchanged. These edits preserve all required identities and incumbent partners.
Their total cost is at most
\(h\sum_{v\in S}(D+\deg_G(v))+h\sum_{w\in T}(D+\deg_G(w))\le2kh(D+n)=\varepsilon.\)
For every \((v,w)\in S\times T\), both edited agents prefer the other’s category to their incumbent category. Each such pair of category groups contributes \(h^2\), giving
\(B(\nu,\omega)\ge h^2|S||T|=h^2k^2=\beta.\)
Thus every yes instance of Balanced Biclique produces a yes instance of the continuous problem.
Suppose \(G\) has no balanced biclique of size \(k\). Consider arbitrary admissible transport plans \(P,Q\) of total cost \(C\le\varepsilon\).
For each active applicant \(a_v\), let \(x_v\) be the fraction of its mass whose destination ranking places at least one graph-neighbor category above its incumbent. Define \(y_w\) symmetrically for active positions.
Thus \(x_v,y_w\in[0,1]\). Every graph neighbor initially lies in position at least \(D+2\). Lemma 2 therefore gives
\(C\ge h(D+1)\left(\sum_vx_v+\sum_wy_w\right).\)
Consequently, with \(\delta=n/D=1/(64k^2)\),
\(\sum_vx_v+\sum_wy_w\le\frac{\varepsilon}{h(D+1)}\le2k(1+\delta).\)
The scaled vectors \(\bar x=x/(1+\delta)\) and \(\bar y=y/(1+\delta)\) satisfy the hypotheses of Lemma 1. Hence
\(F_G(x,y)\le(1+\delta)^2(k^2-\tfrac14).\)
Since \(0<\delta\le1\), we have \((1+\delta)^2\le1+3\delta\), and therefore
\(F_G(x,y)\le k^2-\tfrac14+3\delta k^2=k^2-\tfrac{13}{64}.\)
Call blocking pairs between active category groups \(a_v,b_w\) with \((v,w)\in E\) graph pairs, and let their total density be \(B_{\mathrm{graph}}\).
For a particular graph edge, the applicant mass preferring \(b_w\) to its incumbent is at most \(hx_v\); the corresponding position mass is at most \(hy_w\). Because the density uses product masses,
\(B_{\mathrm{graph}}\le h^2F_G(x,y)\le h^2(k^2-\tfrac{13}{64}).\)
This argument does not require integral activation fractions.
For an active agent, call a category of positive mass far if it is neither the incumbent category nor a graph-neighbor category. For an inactive agent, every category of positive mass other than its incumbent is far.
Every far category initially lies in position at least \(H+2\). For active agents, this follows because all \(H\) barrier categories precede the remaining positive-mass categories; for inactive agents, it follows directly from their ranking definition.
Call a destination ranking far-reaching if it places at least one far category above its incumbent. Let \(R_A\) and \(R_P\) be the total masses assigned to far-reaching rankings on the applicant and position sides.
Lemma 2, applied separately to each transport entry ending in such a ranking, gives
\(C\ge(H+1)(R_A+R_P).\)
A blocking pair that is not a graph pair must have at least one endpoint with a far-reaching ranking. Indeed, if neither endpoint has such a ranking, an inactive endpoint cannot prefer any positive-mass alternative; two active endpoints can mutually prefer each other only along a graph edge.
Let \(B_{\mathrm{other}}\) be the density of all these other blocking pairs. Each side has total mass one, so summing the endpoint-indicator bound against product masses gives
\(B_{\mathrm{other}}\le R_A+R_P\le\frac{C}{H+1}\le\frac{\varepsilon}{H}.\)
By the chosen parameters,
\(\frac{\varepsilon}{H}=\frac{2kh(D+n)}{64k(D+n)N}=\frac{h^2}{32}.\)
Combining the two density bounds yields
\(B(\nu,\omega)\le h^2(k^2-\tfrac{13}{64})+\frac{h^2}{32}=h^2(k^2-\tfrac{11}{64})<h^2k^2=\beta.\)
Thus no admissible real transport of cost at most \(\varepsilon\) reaches the threshold when the source graph has no required biclique.
The construction satisfies every input hypothesis, has polynomial size, and is a yes instance exactly when the source graph contains a balanced biclique of size \(k\). Its soundness proof covers unrestricted destination rankings and arbitrary real mass splitting.
Therefore the continuous blocking-pair-density decision problem is \(\mathrm{NP}\)-hard. A running time polynomial in \(m,\tau,L\) would imply \(\mathrm{P}=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The prover’s reduction is correct. It establishes \(\mathrm{NP}\)-hardness for the exact continuous problem, including arbitrary real mass splitting and destination rankings absent from the input support. I found no major or minor issues.
The source problem is stated precisely: find subsets of size \(k\) in the two specified parts of a bipartite graph whose cross product consists entirely of edges. The introduction of the cited [Peeters paper](https://cgi.di.uoa.gr/~vassilis/co/biclique.pdf) explicitly identifies this balanced biclique problem as \(\mathrm{NP}\)-complete.
Restricting to \(1\le k\le\min\{|V|,|W|\}\) is legitimate: excluded instances can be decided directly. In the retained instances, \(n\ge2\) and \(k\le n/2\), so all subsequent parameter definitions have the required positive denominators.
The prover claims hardness, not membership in \(\mathrm{NP}\) or \(\mathrm{NP}\)-completeness of the continuous problem. Its conclusion stays within that scope.
Every step is valid.
\[
F_G(x,y)\le ab.
\]
From \(a+b\le2k\), multiplication by \(a\ge0\) gives
\[
ab\le a(2k-a)=k^2-(a-k)^2.
\]
Thus \(|a-k|\ge\tfrac12\) yields the claimed gap. The symmetric argument for \(b\) is also correct.
The boundary cases \(|a-k|=\tfrac12\) or \(|b-k|=\tfrac12\) belong to the first cases. The lemma also applies when \(k=1\).
The comparison-counting argument is correct.
The incumbent–target comparison must reverse. For each category initially between them, preserving both its comparison with the incumbent and its comparison with the target would force the incumbent to precede that category and that category to precede the target. This contradicts placing the target above the incumbent.
The comparisons counted for different intermediate categories are distinct, and none is the incumbent–target comparison. Thus at least \(r-1\) comparisons reverse. An adjacent swap changes exactly one unordered comparison, so the Kendall distance is at least \(r-1\).
Applying this lower bound to each destination ranking separately is valid for split transports. It does not impose integrality or any restriction on destination support.
The constructed instance satisfies the task’s hypotheses.
The barrier parameters are valid. In particular,
\[
\frac HD=\frac{64k(D+n)N}{D}>1,
\]
so the first \(D\) barriers and the remaining barriers are well-defined blocks.
The encoding claims are also correct. Since \(D=O(n^3)\), \(N=O(n)\), and \(k=O(n)\), one has \(H=O(n^5)\). Explicitly listing all rankings therefore takes polynomial space and time. The support and category counts are
\[
\tau=2(n+1),\qquad m=2(n+1+H).
\]
All masses, the budget, and the threshold are dyadic rationals of polynomial bit length. The threshold satisfies \(0<\beta<1\), since \(k<N\).
The proposed edits are admissible and meet both constraints.
Moving a selected incumbent below the first barrier block and all graph neighbors crosses exactly \(D+\deg_G(v)\) categories, giving the stated Kendall cost. The symmetric position edit has the same interpretation.
There are \(k\) edited identities on each side, each of mass \(h\), and every degree is at most \(n\). Consequently,
\[
C\le2kh(D+n)=\varepsilon.
\]
For each pair in the selected biclique, both edited rankings place the other agent’s category above the incumbent category. Each such identity pair contributes \(h^2\), and the \(k^2\) identity pairs are distinct. Hence
\[
B(\nu,\omega)\ge h^2k^2=\beta.
\]
The construction preserves incumbent partners throughout these edits.
The activation fractions are well-defined even under arbitrary splitting because each active identity starts with exactly one ranking and total mass \(h\).
Every graph neighbor initially occupies position at least \(D+2\). Lemma 2 therefore charges at least \(D+1\) per unit of activated mass. Summing over the disjoint active identities on both sides gives
\[
C\ge h(D+1)\left(\sum_vx_v+\sum_wy_w\right).
\]
The subsequent bound is correct:
\[
\sum_vx_v+\sum_wy_w
\le2k\frac{D+n}{D+1}
\le2k(1+\delta),
\qquad
\delta=\frac nD=\frac1{64k^2}.
\]
Dividing both vectors by \(1+\delta\) preserves their coordinate bounds and makes their combined sum at most \(2k\). Thus Lemma 1 applies.
The numerical estimate is valid:
\[
(1+\delta)^2\le1+3\delta
\]
for \(0<\delta\le1\), and therefore
\[
F_G(x,y)
\le k^2-\frac14+3\delta k^2
=k^2-\frac{13}{64}.
\]
Dropping the negative term arising from multiplying \(-\tfrac14\) by \(3\delta\) only weakens the bound.
For each graph edge, the mass preferring its particular opposite category is bounded by the corresponding activated mass. Because the task defines density using product masses,
\[
B_{\mathrm{graph}}\le h^2F_G(x,y).
\]
This argument correctly permits arbitrary correlations among preferences within each destination ranking.
The far-category bound accounts for every remaining possible contribution.
For active identities, every positive-mass category outside the incumbent and neighbor blocks comes after all \(H\) barriers. For inactive identities, every positive-mass alternative comes after those barriers. Thus every far category initially has position at least \(H+2\).
Lemma 2 consequently gives
\[
C\ge(H+1)(R_A+R_P).
\]
This bound counts each far-reaching transport entry once, regardless of how many far categories its destination ranking promotes.
The assertion that every nongraph blocking pair has a far-reaching endpoint is correct:
Pairs involving zero-mass categories contribute nothing.
The endpoint-indicator bound gives
\[
B_{\mathrm{other}}\le R_A+R_P,
\]
because the opposite side has total mass one. Possible double counting only enlarges this upper bound.
The parameter calculation is exact:
\[
\frac{\varepsilon}{H}
=\frac{2kh(D+n)}{64k(D+n)N}
=\frac{h^2}{32}.
\]
The activation-cost bound and far-reaching-cost bound are used separately; the proof does not incorrectly add overlapping cost charges.
Graph pairs and all other pairs partition the blocking-density contributions. Combining the verified bounds yields
\[
B(\nu,\omega)
\le h^2\left(k^2-\frac{13}{64}\right)+\frac{h^2}{32}
=h^2\left(k^2-\frac{11}{64}\right)
<\beta.
\]
Thus every source no-instance produces a target no-instance, including for unrestricted real transports. Completeness establishes the converse. The reduction has polynomial output size, so it proves the claimed polynomial-time many-one hardness.
No additional clarification or repair is needed. The output resolves the assigned complexity question by establishing \(\mathrm{NP}\)-hardness.
⟨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.