Answer: \(\mathrm{NP}\text{-complete}\) for the budget-decision version; hence minimum-cost computation is \(\mathrm{NP}\text{-hard}\)
Theorem 3 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateAV-$DelApprovals-VI-Bribery ∈P.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given candidates \(C\), committee size \(k\), preferred candidate \(p\), rational budget \(B\), an ordered population partitioned into \(\tau\) contiguous cohorts of rational masses \(\mu_t\), common approval ballots inducing candidate intervals \(J_c\), and common per-candidate deletion prices \(g_c\), choose final intervals \(J'_c\subseteq J_c\), with \(J'_p=J_p\), minimizing \(\sum_{c\ne p}\int_{J_c\setminus J'_c} g_c\,d\mu\), such that \(p\) belongs to at least one size-\(k\) approval-winning committee; decide whether the optimum is at most \(B\).
Given a candidate order \(C\), let each voter type \(t\in T\) have mass \(\mu_t\in\mathbb{Q}_{\geq 0}\), an initial approval interval \(I_t\subseteq C\), and a deletion price \(\pi_t(c)\in\mathbb{Q}_{\geq 0}\cup\{+\infty\}\) for each \(c\in I_t\). A bribery may split each type's mass among final ballots \(J\), where \(J\) is an empty or contiguous subinterval of \(I_t\): choose \(x_{t,J}\geq0\) with \(\sum_Jx_{t,J}=\mu_t\). Its cost is \(\sum_{t,J}x_{t,J}\sum_{c\in I_t\setminus J}\pi_t(c)\), and candidate \(c\)'s final approval score is \(\operatorname{score}(c)=\sum_{t,J:c\in J}x_{t,J}\). Under approval voting with committee size \(k\), \(p\) can belong to a winning committee exactly when at most \(k-1\) candidates have score strictly greater than \(\operatorname{score}(p)\).
Target. Is this continuous priced deletion-bribery problem solvable in polynomial time, or is it NP-hard?
Nearest known results. The discrete version, with finitely many unit-mass voters, individually priced approval deletions, and the candidate-interval property preserved on the given candidate order, is NP-complete.
The continuous priced deletion-bribery problem is \(\mathrm{NP}\)-complete in its budget-decision form. Consequently, computing the minimum bribery cost is \(\mathrm{NP}\)-hard.
Hardness holds even when all masses are integral, every finite price belongs to \(\{0,1\}\), and the only other price is \(+\infty\). Thus allowing each type to split its mass fractionally does not remove the hardness of the candidate-interval setting.
The reduction below is a fractional-tight adaptation of the \(\operatorname{RX3C}\) construction used for the discrete problem by [Kusek et al.](https://arxiv.org/abs/2209.00368).
Consider the decision problem with a rational budget \(B\).
For a type \(t\), there are at most \(1+|I_t|(|I_t|+1)/2\) possible final ballots: the empty ballot and all contiguous subintervals of \(I_t\). Hence all variables \(x_{t,J}\) can be listed explicitly in polynomial time.
Nondeterministically guess a set \(H\subseteq C\setminus\{p\}\) with \(|H|\leq k-1\). Interpret \(H\) as the candidates permitted to have score strictly greater than \(p\). Feasibility is then expressed by the rational linear program consisting of
\[ \sum_J x_{t,J}=\mu_t \]
for every \(t\),
\[ \sum_{t,J:c\in J}x_{t,J}\leq \sum_{t,J:p\in J}x_{t,J} \]
for every \(c\notin H\cup\{p\}\), together with \(x_{t,J}\geq0\) and the cost bound at most \(B\). Variables corresponding to a final ballot with infinite cost are omitted.
If a successful bribery exists, choose \(H\) to contain all candidates that actually beat \(p\). Conversely, feasibility for some \(H\) immediately gives a successful bribery. Rational linear-program feasibility is polynomial-time decidable, so the problem belongs to \(\mathrm{NP}\).
An instance of Restricted Exact Cover by \(3\)-Sets consists of
\[ X=\{x_1,\ldots,x_{3n}\} \]
and
\[ \mathcal S=\{S_1,\ldots,S_{3n}\}, \]
where every \(S_j\) has size \(3\) and every element of \(X\) belongs to exactly three sets. The question is whether \(X\) has an exact cover consisting of \(n\) members of \(\mathcal S\). This problem is \(\mathrm{NP}\)-complete.
Create the following candidates:
Use the candidate order
\[ s_1,\ldots,s_{3n},d_1,\ldots,d_{2n},x_1,\ldots,x_{3n},p. \]
For every candidate \(c\in\{s_1,\ldots,s_{3n},d_1,\ldots,d_{2n},p\}\), introduce a fixed type of mass \(2\), with initial interval \(\{c\}\) and deletion price \(+\infty\).
For every incidence \(x_i\in S_j\), introduce a solution type \(t_{j,i}\) of mass \(1\), whose initial interval is
\[ I_{j,i}=[s_j,x_i]. \]
Give the two endpoint approvals price \(1\):
\[ \pi_{j,i}(s_j)=\pi_{j,i}(x_i)=1, \]
and give every interior approval price \(0\).
There are \(9n\) solution types because there are \(3n\) sets, each with three elements. Set
\[ k=n+1 \]
and
\[ B=9n. \]
The preferred candidate has fixed score \(2\).
Assume that \(\mathcal F\subseteq\mathcal S\) is an exact cover of size \(n\).
For every incidence \(x_i\in S_j\), choose the final ballot
Each solution type incurs cost exactly \(1\), so the total cost is \(9n=B\).
Every dummy candidate has score \(2\). Each unselected set candidate has score \(2\), while each selected set candidate has score \(5\). Because \(\mathcal F\) is an exact cover, every universe element belongs to exactly one selected set. Consequently, each universe candidate retains approvals from precisely its two incidences with unselected sets and has score \(2\).
Thus exactly the \(n\) selected set candidates have score greater than \(2=\operatorname{score}(p)\). Since \(k-1=n\), candidate \(p\) belongs to a winning committee.
Now suppose that a bribery of cost at most \(9n\) makes \(p\) a winner.
Consider one solution type with interval \([s_j,x_i]\). All interior deletion prices are zero. Therefore every final interval can be replaced, without increasing cost or any candidate’s score, by one of the following four ballots:
Indeed, an interval containing both endpoints is the whole interval. An interval containing exactly one endpoint can be shrunk to that endpoint without changing its cost. An interval containing neither endpoint can be replaced by the empty ballot, again without changing its cost.
For incidence \((j,i)\), let \(f_{j,i}\), \(a_{j,i}\), \(b_{j,i}\), and \(e_{j,i}\) be the mass assigned respectively to these four ballots. They satisfy
\[ f_{j,i}+a_{j,i}+b_{j,i}+e_{j,i}=1. \]
Let
\[ F=\sum_{j,i}f_{j,i}. \]
Every whole interval \([s_j,x_i]\) contains every dummy candidate. Hence each dummy candidate has score \(2+F\). If \(F>0\), all \(2n\) dummy candidates have score strictly greater than \(p\). Since \(2n>n=k-1\), this contradicts that \(p\) is a winner. Therefore
\[ F=0. \]
The cost contributed by incidence type \((j,i)\) is
\[ a_{j,i}+b_{j,i}+2e_{j,i}=1+e_{j,i}, \]
where the equality uses \(f_{j,i}=0\). Summing over all \(9n\) incidence types, the total cost is
\[ 9n+\sum_{j,i}e_{j,i}. \]
The budget is \(9n\), so every \(e_{j,i}\) is zero. Consequently, every incidence type splits its entire mass only between the two endpoint singletons. Write
\[ a_{j,i}\in[0,1] \]
for the mass assigned to \(\{s_j\}\); then \(1-a_{j,i}\) is assigned to \(\{x_i\}\).
For every set \(S_j\), define
\[ A_j=\sum_{x_i\in S_j}a_{j,i}. \]
The score of \(s_j\) is \(2+A_j\). Thus \(s_j\) beats \(p\) exactly when \(A_j>0\). Let \(q\) be the number of such active sets.
For every universe element \(x_i\), define
\[ A_i=\sum_{j:x_i\in S_j}a_{j,i}. \]
Because every element belongs to exactly three sets, the score of \(x_i\) is \(3-A_i\). Hence \(x_i\) beats \(p\) exactly when \(A_i<1\). Let \(b\) be the number of such universe candidates.
The only candidates that can beat \(p\) are the \(q\) active set candidates and these \(b\) universe candidates. Since \(p\) is a winner,
\[ q+b\leq n. \]
Let
\[ A=\sum_j A_j=\sum_i A_i. \]
Only the \(q\) active sets contribute to \(A\), and each contains three variables bounded by \(1\). Therefore
\[ A\leq3q. \]
There are \(3n-b\) universe elements with \(A_i\geq1\), so
\[ A\geq3n-b. \]
Using \(b\leq n-q\), we obtain
\[ 3q\geq A\geq3n-b\geq2n+q. \]
Therefore \(q\geq n\). On the other hand, \(q\leq n\) follows from \(q+b\leq n\). Hence
\[ q=n \]
and
\[ b=0. \]
It follows that \(A\geq3n\), while \(A\leq3q=3n\). Thus \(A=3n\). Every active set contributes at most \(3\), and there are exactly \(n\) active sets, so every active set contributes exactly \(3\). Therefore
\[ a_{j,i}=1 \]
for every incidence belonging to an active set. Inactive sets have all their corresponding variables equal to \(0\).
Finally, \(b=0\) means that every universe element has \(A_i\geq1\), so every element belongs to at least one active set. The \(n\) active sets contain exactly \(3n\) incidences altogether, equal to the size of \(X\). Hence every element belongs to exactly one active set. The active sets form an exact cover.
The constructed continuous instance is feasible within budget if and only if the \(\operatorname{RX3C}\) instance has an exact cover. The construction has polynomial size, so continuous priced deletion bribery is \(\mathrm{NP}\)-hard. Together with membership in \(\mathrm{NP}\), the budget-decision problem is \(\mathrm{NP}\)-complete.
⟨structured verdict parsed — rendered above⟩
The reduction is correct and establishes NP-hardness of the continuous problem despite fractional mass splitting. The membership argument also correctly places the rational budget-decision problem in NP.
There is one minor edge-case defect: the soundness proof uses \(2n>n\), which is false when \(n=0\). This does not affect the NP-hardness direction once the reduction is explicitly restricted to nonempty RX3C instances, but that restriction is not stated.
For each type \(t\), the number of permitted final ballots is indeed
\[ 1+\frac{|I_t|(|I_t|+1)}2, \]
so the proposed LP has polynomially many variables and constraints.
Guessing \(H\) with \(|H|\leq k-1\) is sufficient:
Omitting variables whose ballot has infinite deletion cost is valid for a finite rational budget. Rational LP feasibility is decidable in polynomial time. Thus the NP-membership argument is sound.
The construction has polynomial size:
Every initial ballot is contiguous in the displayed candidate order. In particular, every interval \([s_j,x_i]\) contains all dummy candidates because every \(s_j\) precedes the dummy block and every \(x_i\) follows it.
The fixed singleton types force score \(2\) for \(p\), every set candidate, and every dummy candidate.
Given an exact cover:
Exactly \(n=k-1\) candidates beat \(p\), so completeness is correct.
The four stated ballot forms exhaust the relevant cases after score-nonincreasing replacement:
These replacements only decrease approval scores. They do not decrease \(p\)'s score because no solution interval contains \(p\). Thus they preserve successfulness, although this last preservation observation is implicit rather than stated.
Every whole-interval mass approves every dummy, so each dummy has score \(2+F\). For \(n\geq1\), \(F>0\) would produce \(2n>n=k-1\) candidates beating \(p\), forcing \(F=0\).
With \(f_{j,i}=0\), the computation
\[ a_{j,i}+b_{j,i}+2e_{j,i}=1+e_{j,i} \]
follows from \(a_{j,i}+b_{j,i}+e_{j,i}=1\). Hence total cost is \(9n+\sum e_{j,i}\), and the budget forces every \(e_{j,i}=0\). The endpoint-splitting normal form is therefore correctly derived.
After normalization:
Thus \(q+b\leq n\).
The double-counting identity
\[ A=\sum_j A_j=\sum_i A_i \]
is correct. The bounds
\[ A\leq3q \]
and
\[ A\geq3n-b \]
are also correct. Combining them with \(b\leq n-q\) gives
\[ 3q\geq2n+q, \]
hence \(q\geq n\). Together with \(q\leq n\), this yields \(q=n\) and \(b=0\).
It then follows that \(A=3n\). Equality in the upper bound forces every active set's three variables to equal \(1\), while inactive sets have all three variables equal to \(0\). Finally, \(b=0\) ensures every element is covered by at least one active set, and the \(n\) active triples have exactly \(3n\) total incidences. Therefore every element is covered exactly once. This extraction is rigorous.
The claim \(2n>n\) silently assumes \(n\geq1\). As RX3C was stated without excluding \(n=0\), that displayed inequality is not universally true. The minimum repair is to state that the reduction is from the NP-hard restriction to instances with \(n\geq1\), or explicitly dispose of the empty instance before applying the construction.
No major issue affects the NP-hardness or NP-completeness conclusion.
⟨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.