Answer: \(\mathsf{NP}\)-complete even for \(k=1\); \(\mathsf{FPT}\) parameterized by \(k\) if and only if \(\mathsf P=\mathsf{NP}\).
Theorem 2 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateProportionality by Item Deletion is W[3]-hard when pa- rameterized by the size k of the desired solution.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finite good classes \(G\), a rational distribution \(\mu\) over supported ranking types \(T\), and rational per-capita supplies \(s_g\), choose deletion masses \(d_g\) and a distribution \(x_{t,b}\) over integral bundles \(b\in\mathbb{Z}_{\ge 0}^{G}\). Require \(0\le d_g\le s_g\), \(\sum_b x_{t,b}=\mu_t\), \(\sum_{t,b}x_{t,b}b_g=s_g-d_g\), and, for every bundle assigned positive mass to type \(t\), \(\sum_{g\in P_t(j)}b_g\ge\left\lceil\sum_{g\in P_t(j)}(s_g-d_g)\right\rceil\) for each ranked prefix \(P_t(j)\). Minimize \(\sum_g d_g\), or decide whether it is at most a given rational budget \(\kappa\).
Let \(G\) be a nonempty set of \(m\) good classes. Each type \(t\) has a strict linear ranking of all classes; \(P_t(j)\) is its set of first \(j\) classes, for \(1\le j\le m\).
A society is given by its support: the list \(T\) of \(\tau\) types with positive mass, each mass \(\mu_t\) a binary rational, with \(\sum_{t\in T}\mu_t=1\). Here \(\tau\) is the support size, not the number of possible rankings.
Inputs also include nonnegative binary-rational per-capita supplies \(s_g\) and a nonnegative binary-rational deletion budget \(\kappa\). Let \(L\) be the total input bit length and \(k=\lceil\kappa\rceil\).
Choose real deletion masses \(0\le d_g\le s_g\) and nonnegative real assignment masses \(x_{t,b}\), indexed by \(t\in T\) and integral bundles \(b\in\mathbb Z_{\ge0}^{G}\), satisfying \(\sum_bx_{t,b}=\mu_t\) and \(\sum_{t,b}x_{t,b}b_g=s_g-d_g\) for every \(g\in G\).
For every \(x_{t,b}>0\) and every \(1\le j\le m\), require \(\sum_{g\in P_t(j)}b_g\ge\left\lceil\sum_{g\in P_t(j)}(s_g-d_g)\right\rceil\). These requirements apply to each assigned bundle, rather than only to its expectation. Deleting all supplies and assigning empty bundles is permitted.
The decision problem asks whether such an assignment exists with \(\sum_gd_g\le\kappa\).
Is this decision problem in \(\mathsf P\), with running time polynomial in \(m,\tau,L\), or is it \(\mathsf{NP}\)-hard? If it is \(\mathsf{NP}\)-hard, is it nevertheless \(\mathsf{FPT}\) parameterized by \(k\), with running time \(f(k)(m+\tau+L)^{O(1)}\)?
For finitely many agents with strict rankings of individual items, proportionality by item deletion is \(\mathsf{NP}\)-complete and \(\mathsf W[3]\)-hard parameterized by the number of deletions; it is polynomial-time solvable for three agents. [Verified results](https://link.springer.com/article/10.1007/s00453-020-00794-4).
No result settling the exact mass problem defined above was identified in the literature search.
Result. The decision problem is \(\mathsf{NP}\)-complete, even when \(k=1\). Consequently, an algorithm with running time \(f(k)(m+\tau+L)^{O(1)}\) exists if and only if \(\mathsf P=\mathsf{NP}\).
The reduction below explicitly handles real deletion masses. All input masses and supplies in the reduction are equal dyadic rationals.
1. Two preliminary facts. Write \(r_g=s_g-d_g\) for retained supplies, and write \(r(A)=\sum_{g\in A}r_g\).
First, every feasible assignment satisfies \(r(G)\in\mathbb Z_{\ge0}\), and every positively assigned bundle has exactly \(r(G)\) items. Indeed, the last-prefix requirement gives
\(\displaystyle |b|\ge\lceil r(G)\rceil.\)
The assignment masses sum to one, while their average bundle size is \(r(G)\). Thus \(r(G)\ge\lceil r(G)\rceil\), proving integrality. The nonnegative excesses \(|b|-r(G)\) have weighted sum zero, so each positively assigned bundle has size \(r(G)\).
Second, suppose a type \(t\) ranks \(g\) first and \(s_g=\mu_t\). Then
\(\displaystyle r_g\in\{0,s_g\}.\)
To prove this, assume \(r_g>0\). Every bundle assigned to \(t\) contains at least one copy of \(g\). Consequently,
\(\displaystyle r_g=\sum_{u,b}x_{u,b}b_g\ge\sum_bx_{t,b}=\mu_t=s_g.\)
Since \(r_g\le s_g\), equality holds throughout. Therefore every bundle assigned positively to \(t\) contains exactly one copy of \(g\), and every bundle assigned positively to another type contains none. We will use this observation to force certain classes to be either fully retained or fully deleted.
2. Source problem and construction. We reduce from the \(\mathsf{NP}\)-complete Set Cover problem: given a universe \(E\), indexed sets \(S_1,\ldots,S_{n_0}\), and a budget \(K\), decide whether at most \(K\) sets cover \(E\). This is one of the problems in [Karp’s NP-completeness theorem](https://www.cs.umd.edu/~gasarch/BLOGPAPERS/Karp.pdf).
We may restrict to instances with nonempty \(E\), every element contained in some set, and \(1\le K\le n_0\): excluded cases are immediately decidable. Append \(n_0\) empty sets. The resulting indexed family has \(n=2n_0\) sets, so \(n\ge2K\), without changing the answer.
For each \(e\in E\), define
\(\displaystyle C_e=\{i\in\{1,\ldots,n\}:e\in S_i\}.\)
Thus \(1\le |C_e|\le n\). Put \(u=|E|\) and \(R=n+1\).
There will be \(n\) guard types and the following checker types:
Choose \(N\) to be the smallest power of two satisfying
\(\displaystyle N\ge n+(u+2)R.\)
Add exactly \(N-n-(u+2)R\) fillers. Thus there are \(N\) types altogether, and \(p=N-n\) checker types. Let \(\mathcal A\) denote their index set and put \(c=1/N\). Every type has mass \(c\).
The good classes are the following disjoint sets:
\(\displaystyle V=\{v_1,\ldots,v_n\},\qquad H=\{h_1,\ldots,h_n\},\)
\(\displaystyle F=\{f_\alpha:\alpha\in\mathcal A\},\qquad W=\{w_\alpha:\alpha\in\mathcal A\},\qquad Z=\{z_1,\ldots,z_K\}.\)
Every class has supply \(c\). Hence the number of classes is \(2N+K\), and total supply is
\(\displaystyle s(G)=(2N+K)c=2+Kc.\)
Set the deletion budget to \(\kappa=Kc\). Since \(0<K<N\), its parameter is \(k=\lceil\kappa\rceil=1\).
Choose disjoint subsets \(H^0,H^1\subseteq H\), each of size \(K\); this is possible because \(n\ge2K\). For each \(e\in E\), choose any \(H_e\subseteq H\) of size
\(\displaystyle |H_e|=n-|C_e|+1.\)
Fix an arbitrary ordering within every listed set. Rankings are as follows.
The guard type \(\gamma_i\) ranks \(v_i\) first, \(h_i\) second, all classes in \(Z\) next, and then every remaining class.
Every checker \(\alpha\) ranks, in order:
For the first selection group, set \(A_\alpha=V\cup H^0\); for the second, set \(A_\alpha=V\cup H^1\). In the verification group for \(e\), set
\(\displaystyle A_\alpha=\{v_i:i\in C_e\}\cup H_e.\)
For fillers, set \(A_\alpha=\varnothing\).
These prescriptions give strict linear rankings of all classes. Different types have different first classes, so the support size is exactly \(\tau=N\). All numbers are dyadic rationals, and \(N\), the rankings, and their encoding lengths are polynomial in the source input size.
3. Any feasible assignment yields a set cover. Suppose the constructed instance has a feasible assignment within budget.
By the first preliminary fact, retained total supply is an integer. The budget and initial total imply
\(\displaystyle 2\le r(G)\le2+Kc<3.\)
Therefore
\(\displaystyle r(G)=2,\qquad \sum_gd_g=Kc.\)
In particular, every positively assigned bundle has exactly two items.
We first prove that every class in \(F\) is fully retained. By the second preliminary fact, each \(f_\alpha\) is either fully retained or fully deleted. They cannot all be deleted, since their total supply is \(pc>Kc\).
If some \(f_\alpha\) were deleted, consider the first retained class \(f_\beta\) in checker \(\alpha\)’s ranking. It exists and occurs within the initial block of \(F\)-classes. All preceding classes have zero retained supply, so every bundle assigned to \(\alpha\) must contain \(f_\beta\). But checker \(\beta\), which ranks \(f_\beta\) first, already consumes its entire supply \(c\). This is impossible.
Thus all \(F\)-classes are retained. Each checker receives exactly one copy of its own \(f_\alpha\) in every assigned bundle, and nobody else receives that class.
Similarly, because guard \(\gamma_i\) ranks \(v_i\) first, each \(v_i\) is either fully retained or fully deleted. Whenever retained, its entire supply is consumed by \(\gamma_i\). Hence no checker receives any class in \(V\).
We next prove that all deletion occurs in \(V\). For \(\ell\in\{0,1\}\), define
\(\displaystyle Q^\ell=F\cup V\cup H^\ell.\)
This is a prefix set for every checker in selection group \(\ell\). If \(r(Q^\ell)>1\), every assigned bundle of each of these \(R\) checkers must contain at least two items from \(Q^\ell\).
Such a checker receives exactly one item from \(F\) and none from \(V\). Therefore every assigned bundle must contain at least one item from \(H^\ell\). Aggregating over the group gives
\(\displaystyle r(H^\ell)\ge Rc.\)
But \(r(H^\ell)\le Kc<Rc\), a contradiction. Consequently \(r(Q^\ell)\le1\).
The initial supply in \(Q^\ell\) is
\(\displaystyle s(Q^\ell)=(p+n+K)c=1+Kc.\)
Thus \(d(Q^\ell)\ge Kc\). Total deletion is exactly \(Kc\), so nothing outside \(Q^\ell\) is deleted. Applying this to both selection groups confines all deletion to
\(\displaystyle Q^0\cap Q^1=F\cup V.\)
As \(F\) is fully retained, all deletion occurs in \(V\). Each deleted \(v_i\) costs exactly \(c\), so
\(\displaystyle D=\{i:r_{v_i}=0\}\)
has exactly \(K\) elements.
Finally, fix \(e\in E\). For its verification group, the set
\(\displaystyle Q_e=F\cup\{v_i:i\in C_e\}\cup H_e\)
is a prefix. Its retained supply is
\(\displaystyle r(Q_e)=(p+|C_e|+|H_e|)c-|D\cap C_e|c =1+c-|D\cap C_e|c.\)
If \(D\cap C_e=\varnothing\), then \(r(Q_e)=1+c>1\). Every assigned bundle of each of the \(R\) verification checkers must consequently contain at least two items from \(Q_e\). Again, it contains exactly one \(F\)-item and no \(V\)-item, so it must contain an \(H_e\)-item. This would require
\(\displaystyle r(H_e)\ge Rc=(n+1)c,\)
whereas \(r(H_e)\le |H_e|c\le nc\). This contradiction proves \(D\cap C_e\ne\varnothing\).
Thus the sets indexed by \(D\) cover every element of \(E\).
4. A set cover yields a feasible assignment. Conversely, suppose the source instance has a cover of size at most \(K\). Extend its index set to a set \(D\) of exactly \(K\) indices. It remains a cover.
Delete exactly the classes \(v_i\) with \(i\in D\), and retain everything else. Total deletion is \(Kc=\kappa\), and retained total supply is two.
Assign one bundle to each type, with assignment mass \(c\):
Every retained class is used exactly once across these bundles. Since each type has mass \(c\), all supply equalities hold.
It remains to check every prefix requirement.
For an unselected guard, its two assigned items occupy its first two positions. Its first prefix has retained supply \(c\), and every later prefix contains both assigned items and has retained supply at most two. All requirements hold.
For a selected guard, \(v_i\) has zero retained supply. Before its assigned reserve class \(z_{\ell(i)}\), the ranking contains only \(v_i,h_i\), and reserve classes. Their total retained supply is at most
\(\displaystyle (K+1)c\le1.\)
The zero-supply initial prefix needs no item; thereafter the guard already has \(h_i\). Once its assigned reserve class appears, it has both items, satisfying every subsequent prefix because total retained supply is two.
For a checker, consider the prefix immediately before its own \(w_\alpha\). Its retained supply is:
\(\displaystyle r(Q^\ell)=1+Kc-|D|c=1.\)
\(\displaystyle r(Q_e)=1+c-|D\cap C_e|c\le1.\)
\(\displaystyle r(F)=pc<1.\)
Every earlier prefix has retained supply at most one, and the checker’s first-ranked assigned item \(f_\alpha\) is already present. At and after \(w_\alpha\), both assigned items are present, and every prefix has retained supply at most two.
Thus every bundle satisfies every ceiling requirement. This completes the reduction and proves \(\mathsf{NP}\)-hardness on instances with \(k=1\).
5. Membership in \(\mathsf{NP}\). We prove membership for the full problem, including arbitrary binary-rational inputs and real assignment masses.
Consider any feasible assignment and let \(q=r(G)\). By the first preliminary fact, every positively assigned bundle has size \(q\). There are only finitely many such integral bundles. Moreover, \(q\le s(G)\), so every bundle coordinate has bit length polynomial in the input length.
Associate with each used pair \((t,b)\) the vector
\(\displaystyle v_{t,b}=(e_t,b)\in\mathbb R^{\tau+m},\)
where \(e_t\) is the type’s standard basis vector. The assignment expresses \((\mu,r)\) as a nonnegative linear combination of these vectors.
This combination can be reduced to at most \(\tau+m\) vectors. Indeed, whenever more vectors have positive coefficients, they are linearly dependent. A dependence has coefficients of both signs, because summing its first \(\tau\) coordinates gives zero. Subtract a suitable multiple of the dependence from the assignment coefficients until at least one coefficient becomes zero, preserving nonnegativity and \((\mu,r)\). Repeat.
Fix the resulting pairs \((t_i,b^i)\), indexed by \(1\le i\le J\), where \(J\le\tau+m\). For these pairs, consider the following linear system in weights \(a_i\) and retained supplies \(r_g\):
\(\displaystyle a_i\ge0,\qquad \sum_{i:t_i=t}a_i=\mu_t,\qquad r_g=\sum_i a_i b^i_g,\)
\(\displaystyle 0\le r_g\le s_g,\qquad \sum_g r_g\ge\sum_g s_g-\kappa,\)
and, for every selected pair and every prefix,
\(\displaystyle r(P_{t_i}(j))\le\sum_{g\in P_{t_i}(j)}b^i_g.\)
The last inequalities are exactly the required ceiling inequalities, since their right sides are integers.
This rational linear system is feasible: the reduced original assignment satisfies it. Its feasible region is bounded, because \(a_i\le\mu_{t_i}\le1\) and \(0\le r_g\le s_g\).
A nonempty bounded rational polyhedron has a vertex. Here both the dimension and all coefficient bit lengths are polynomial in the input length. Clearing denominators in the tight constraints and applying Cramer’s rule shows that a vertex has polynomial bit length: for dimension \(D\) and integer coefficient bit bound \(B\), the relevant determinants have bit length \(O(D(B+\log D))\).
Therefore a certificate consists of at most \(\tau+m\) integral bundles, their type indices, and polynomial-length rational weights and retained supplies. All displayed equalities and inequalities can be verified by exact rational arithmetic in polynomial time. The problem belongs to \(\mathsf{NP}\).
6. Complexity consequence. The problem is therefore \(\mathsf{NP}\)-complete even on the slice \(k=1\). An \(\mathsf{FPT}\) algorithm would run on that slice in time \(f(1)(m+\tau+L)^{O(1)}\), yielding a polynomial-time algorithm for Set Cover and hence implying \(\mathsf P=\mathsf{NP}\). Conversely, if \(\mathsf P=\mathsf{NP}\), membership in \(\mathsf{NP}\) supplies a polynomial-time algorithm, which is also \(\mathsf{FPT}\).
⟨structured verdict parsed — rendered above⟩
The prover’s output resolves the task. The reduction establishes \(\mathsf{NP}\)-hardness with \(k=1\), and the certificate argument establishes membership in \(\mathsf{NP}\) for the full problem. I found no major or minor issues.
1. Preliminary facts.
The retained-total integrality argument is correct. Assignment masses sum to one, so averaging the last-prefix requirement gives
\[
r(G)\ge \lceil r(G)\rceil.
\]
Since the reverse inequality always holds, \(r(G)\) is an integer. The weighted sum of the nonnegative excesses \(|b|-r(G)\) is zero, which forces every positively assigned bundle to have exactly \(r(G)\) items. The argument also covers \(r(G)=0\).
The second fact correctly forces a class to be fully retained or fully deleted when its supply equals the mass of a type ranking it first. If \(r_g>0\), that type’s bundles each require at least one copy, exhausting the available supply. Equality then forces exactly one copy in each of its positively assigned bundles and zero copies for every other type. This argument permits real deletion and assignment masses.
2. Source problem and construction.
The cited Set Cover decision problem is an appropriate \(\mathsf{NP}\)-complete source. Its formulation agrees with the standard Set Cover problem in [Karp’s paper](https://www.cs.umd.edu/~gasarch/BLOGPAPERS/Karp.pdf).
The restriction to nonempty universes, covered elements, and \(1\le K\le n_0\) excludes only immediately decidable cases. Appending empty sets preserves the answer and ensures \(n\ge2K\).
All construction requirements are satisfied:
The least qualifying power of two \(N\) is polynomially bounded in the source size. Consequently, explicitly listing all rankings takes polynomial space and time. The rational quantities have polynomial encoding length.
Finally, \(0<K<N\), so \(\kappa=K/N\) satisfies \(0<\kappa<1\), giving \(k=1\).
3. Feasibility forces exactly \(Kc\) deletion and two-item bundles.
The budget gives \(r(G)\ge2\), while the initial supply gives \(r(G)\le2+Kc<3\). Retained-total integrality therefore forces \(r(G)=2\), total deletion \(Kc\), and exactly two items in every positively assigned bundle. Each conclusion follows directly from the preliminary fact.
4. The argument retaining all \(F\)-classes is valid.
Each \(f_\alpha\) is either fully retained or fully deleted. Since \(p\ge(u+2)(n+1)>K\), deleting every \(F\)-class would exceed the budget.
If \(f_\alpha\) were deleted, checker \(\alpha\)’s first retained \(F\)-class would occur after only zero-retained-supply classes. The corresponding prefix would require that class in every bundle assigned to \(\alpha\). Its owner already consumes its entire supply, giving the stated contradiction.
Thus every checker consumes exactly one copy of its own \(F\)-class in every assigned bundle, and no other type receives that class. The analogous conclusion for retained \(V\)-classes is also valid; in particular, checkers receive no \(V\)-items.
5. The selection groups correctly confine deletion to \(V\).
Each \(Q^\ell\) is an actual prefix of every checker in selection group \(\ell\).
If \(r(Q^\ell)>1\), its ceiling requirement forces two items from that prefix. A checker has exactly one \(F\)-item and no \(V\)-items, so each bundle must contain an \(H^\ell\)-item. The group therefore requires at least \(Rc\) supply from \(H^\ell\), contradicting its maximum supply \(Kc<Rc\).
Hence \(r(Q^\ell)\le1\). Since \(s(Q^\ell)=1+Kc\), deletion inside each \(Q^\ell\) is at least \(Kc\). Total deletion is exactly \(Kc\), and deletion masses are nonnegative, so nothing outside either prefix is deleted.
Their intersection is \(F\cup V\), because \(H^0\cap H^1=\varnothing\). Since \(F\) is retained, all deletion occurs in \(V\). The previously established indivisibility of each \(v_i\) then gives exactly \(K\) deleted indices.
6. The verification groups correctly enforce coverage.
The prefix supply calculation
\[
r(Q_e)=1+c-|D\cap C_e|c
\]
is correct.
If \(D\cap C_e=\varnothing\), every checker in that group requires an \(H_e\)-item in every assigned bundle. This demands at least \((n+1)c\) supply, while \(H_e\) has at most \(nc\). The contradiction proves that every element is covered by a deleted index.
This establishes the soundness direction of the reduction.
7. The converse assignment satisfies all constraints.
Extending a cover to exactly \(K\) indices is possible and preserves coverage. The proposed bundles use every retained class exactly once, including all \(K\) reserve classes, so the supply equalities hold.
The prefix checks cover every position:
Nonnegativity of retained supplies justifies the monotonicity used in these checks. Total retained supply two bounds every subsequent prefix.
Thus the completeness direction is valid.
8. Membership in \(\mathsf{NP}\) is established for arbitrary inputs.
The integral bundle size \(q\le s(G)\) gives polynomial bit length for every bundle coordinate, even if \(q\) is numerically large. For fixed \(q\), there are finitely many possible bundles.
The support reduction to at most \(\tau+m\) vectors is correct. Any dependence among the vectors \((e_t,b)\) has coefficients summing to zero, hence has both signs. The stated elimination preserves nonnegativity, type masses, and retained supplies.
The resulting rational linear system is feasible and bounded. Its prefix inequalities are equivalent to the ceiling requirements because bundle prefix counts are integers. Imposing them also on selected pairs whose new weights become zero does not invalidate the certificate argument: the original reduced assignment satisfies all these inequalities, and zero-weight pairs need no assignment constraints.
The bounded-polyhedron vertex theorem applies. The number of variables, number of constraints, and coefficient bit lengths are polynomial. The denominator-clearing and determinant bound therefore give a rational feasible certificate of polynomial size. Exact verification is polynomial-time.
9. Complexity consequence and feedback.
Hardness on the fixed slice \(k=1\) makes any claimed \(\mathsf{FPT}\) algorithm a polynomial-time algorithm for Set Cover. Conversely, if \(\mathsf P=\mathsf{NP}\), the established membership supplies a polynomial-time algorithm and hence an \(\mathsf{FPT}\) algorithm.
No additional clarification or repair is needed.
⟨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.