Answer: \(\mathrm{NP}\)-complete for each fixed rule \(\mathrm{CSR}\) and \(\mathrm{LSR}\), already with equal masses.
Theorem 3 (∗) — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateCONST-f CSR/f LSR LINK BRIBERY is NP- complete and W[2]-hard with respect to ℓ. Apart from the parameter budget ℓ, which might be small in most applications as only agents which are close to the boundary of being socially (dis)qualified might be interested in their precise margin, another natural parameter is the set of agents we want to make socially qualified, i.e., |A+|. This parameter may also be not too large in most applications, as one is usually only interested in the classification of a limited number of agents.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite type set \(T\), positive rational masses \(\mu_t\) summing to \(1\), a binary qualification matrix \(q:T\times T\to\{0,1\}\), target types \(P\subseteq T\), a rule \(r\in\{\mathrm{CSR},\mathrm{LSR}\}\), and a rational budget \(B\), is there a set \(D\subseteq T\times T\) of type-pair qualifications to flip, with cost \(\sum_{(t,u)\in D}\mu_t\mu_u\le B\), such that every target type is eventually socially qualified under \(r\)?
A society is given by its support: a nonempty list \(T\) of \(\tau\) types with positive binary rational masses \(\mu_t\), summing to \(1\). Here \(\tau\) is the support size, not the number of possible types. There is no separate candidate set or parameter \(m\).
The input also contains an explicit matrix \(q:T\times T\to\{0,1\}\), where \(q(t,u)=1\) means that type \(t\) qualifies type \(u\), targets \(P\subseteq T\), a rule \(r\in\{\mathrm{CSR},\mathrm{LSR}\}\), and a nonnegative binary rational budget \(B\).
Choose \(D\subseteq T\times T\), including diagonal pairs if desired, and set \(q'(t,u)=1-q(t,u)\) on \(D\), leaving other entries unchanged. Each flip changes the entire type pair; types cannot be split and partial flips are unavailable. Its cost is \(\sum_{(t,u)\in D}\mu_t\mu_u\).
Under liberal-start-respecting \(\mathrm{LSR}\), initialize \(K_0=\{u:q'(u,u)=1\}\); under consensus-start-respecting \(\mathrm{CSR}\), initialize \(K_0=\{u:\forall t\in T,\ q'(t,u)=1\}\).
For either rule, iterate \(K_{i+1}=K_i\cup\{u:\exists t\in K_i,\ q'(t,u)=1\}\) until stabilization, obtaining \(K_\infty\). The decision problem asks whether some \(D\) has cost at most \(B\) and satisfies \(P\subseteq K_\infty\); other types are unrestricted.
State running times in \(\tau\), the total input bit length \(L\), and any additional parameters used, such as \(|P|\).
For each fixed rule \(r\in\{\mathrm{CSR},\mathrm{LSR}\}\), is this mass-weighted constructive link-bribery decision problem in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard?
Discrete constructive link bribery is \(\mathrm{NP}\)-complete for both rules and \(\mathrm{W}[2]\)-hard parameterized by the number of flipped qualifications. [Verified result](https://link.springer.com/article/10.1007/s10458-023-09597-7).
No result settling the specified mass-weighted problem was verified.
For each fixed rule \(\mathrm{CSR}\) and \(\mathrm{LSR}\), the specified mass-weighted constructive link-bribery problem is \(\mathrm{NP}\)-complete, already when all masses are equal. Consequently, a polynomial-time algorithm would imply \(\mathrm{P}=\mathrm{NP}\).
The whole-type restriction is essential to the following reduction: each discrete agent becomes one support type, and each discrete qualification flip becomes one whole-type-pair flip.
The verified discrete problem takes a nonempty agent set \(A\), an explicit qualification matrix, constructive targets \(P\subseteq A\), and an integer budget \(k\). It asks whether changing at most \(k\) matrix entries makes every target socially qualified. Diagonal entries may be changed, and agents outside \(P\) are unrestricted.
For either fixed rule, this problem is \(\mathrm{NP}\)-complete by [Theorem 3 of *Fine-grained view on bribery for group identification*](https://link.springer.com/article/10.1007/s10458-023-09597-7). Its rule definitions identify socially qualified agents by reachability from self-qualifying agents under \(\mathrm{LSR}\), or universally qualified agents under \(\mathrm{CSR}\), matching the task.
Fix either rule \(r\). Given a discrete instance with \(n=|A|\), construct the mass-weighted instance by setting
\(T=A,\qquad \tau=n,\qquad \mu_t=\frac1n\ \text{for every }t\in T,\qquad B=\frac{k}{n^2}.\)
Copy the qualification matrix, targets, and rule unchanged, translating qualification values to binary values if necessary.
Every mass is positive, and their sum is \(1\). The rational numbers have binary encodings of polynomial length. The construction introduces no additional types.
For every flip set \(D\subseteq T\times T\), including possible diagonal flips, its mass-weighted cost is
\(\displaystyle \operatorname{cost}(D)=\sum_{(t,u)\in D}\mu_t\mu_u=\frac{|D|}{n^2}.\)
Therefore,
\(\displaystyle \operatorname{cost}(D)\leq B\quad\Longleftrightarrow\quad |D|\leq k.\)
The modified qualification matrices are identical in the two instances. Since neither initialization nor propagation uses masses, their initial sets agree, and induction on the iteration index shows that every subsequent qualified set agrees. Thus their final qualified sets agree as well.
It follows that a flip set is successful and within budget in the discrete instance if and only if it is successful and within budget in the mass-weighted instance. This proves a polynomial-time many-one reduction for each fixed rule.
If the discrete input has bit length \(N\), the constructed input has length \(L=O(N+\tau\log(\tau+1))\). A conservative implementation bound for the reduction is \(O((N+\tau\log(\tau+1))^2)\) bit operations. Hence both mass-weighted problems are \(\mathrm{NP}\)-hard.
A certificate is the flip set \(D\), represented by \(\tau^2\) indicator bits.
Write the input masses and budget as \(\mu_t=a_t/b_t\) and \(B=c/d\), with positive integer denominators. Define
\(\displaystyle Q=\prod_{t\in T}b_t,\qquad w_t=a_t\frac{Q}{b_t}.\)
These are integers, and \(\mu_t=w_t/Q\). Consequently, the budget condition is exactly the integer comparison
\(\displaystyle d\sum_{(t,u)\in D}w_tw_u\leq cQ^2.\)
The bit length of \(Q\) is \(O(L)\), because it is bounded by the sum of the input denominator bit lengths. Moreover, \(\mu_t\leq1\) gives \(w_t\leq Q\). Every intermediate integer in the comparison therefore has \(O(L+\log(\tau+1))=O(L)\) bits. Using schoolbook arithmetic, the cost can be checked in \(O(\tau^2L^2)\) bit operations.
After applying the flips, compute the initial set and perform a graph search from it. Checking consensus initialization and scanning the explicit adjacency matrix take \(O(\tau^2)\) time; liberal initialization takes \(O(\tau)\). The search computes precisely the iterative closure in the task. Finally, check membership of every target.
Thus verification takes \(O(\tau^2L^2)\) bit operations for either rule, proving membership in \(\mathrm{NP}\).
Combining the reduction with polynomial verification proves \(\mathrm{NP}\)-completeness for both fixed rules.
For completeness, enumerating all flip sets gives a deterministic decision algorithm in \(O(2^{\tau^2}\tau^2L^2)\) bit operations. No additional parameter is needed for the classification. The reduction copies \(P\) unchanged and makes no claim of hardness for a fixed target-set size \(|P|\).
⟨structured verdict parsed — rendered above⟩
The prover’s claim is correct: both fixed-rule problems are \(\mathrm{NP}\)-complete, already with equal masses. The cited hardness result applies to the stated model, the reduction preserves feasibility exactly, and the certificate verification has polynomial bit complexity. No major or minor issues were found.
Theorem 3 of [*Fine-grained view on bribery for group identification*](https://link.springer.com/article/10.1007/s10458-023-09597-7) states that constructive link bribery is \(\mathrm{NP}\)-complete for both \(\mathrm{CSR}\) and \(\mathrm{LSR}\).
The paper’s definitions in Sections 2.1–2.2 match the premise stated by the prover: unit-cost link bribery counts changed matrix entries; diagonal entries are available; constructive success requires inclusion of the target set and imposes no restriction on other agents. The paper explicitly characterizes the rules by reachability from self-qualifying agents and universally qualified agents, respectively. Thus the theorem concerns the required source problem, rather than agent bribery, exact bribery, or destructive bribery.
The change from qualification values in \(\{-1,1\}\) to values in \(\{0,1\}\) preserves both qualifications and flips. There is no unverified hypothesis in this application.
Setting \(T=A\) and \(\tau=n\) introduces exactly one support type per discrete agent. Every mass \(1/n\) is positive, and the masses sum to \(1\). The budget \(k/n^2\) is a nonnegative rational for the source problem’s nonnegative integer budget.
Binary rational encoding permits the numerator–denominator representation of \(1/n\); it does not require a terminating binary expansion. Each mass therefore has encoding length \(O(\log(n+1))\). The budget’s encoding length is \(O(\log(k+1)+\log(n+1))\), with the source budget already accounted for in \(N\).
Consequently, the stated output-length bound \(L=O(N+\tau\log(\tau+1))\) is valid. The conservative quadratic bit-operation bound for constructing the output is also sufficient.
For every permitted flip set \(D\), including diagonal pairs, each flipped pair costs \(1/n^2\). Therefore the displayed identity
\(\operatorname{cost}(D)=|D|/n^2\)
is correct. Since \(n>0\), the equivalence between \(\operatorname{cost}(D)\leq k/n^2\) and \(|D|\leq k\) follows exactly, without rounding.
The qualification matrices after corresponding flips agree entry by entry. Initialization depends only on these matrices, and propagation likewise depends only on qualified types and qualification entries. The prover’s induction therefore establishes agreement of all qualified sets and their final closures.
These observations cover arbitrary flip sets in both directions. The reduction neither restricts solutions to additions nor assumes that diagonal entries remain fixed. Hence it is a valid polynomial-time many-one reduction for each fixed rule.
The explicit matrix ensures that \(\tau^2\) certificate bits are polynomial in the input length.
With positive denominators, \(Q=\prod_t b_t\) is positive and divisible by every \(b_t\). Thus each \(w_t=a_t(Q/b_t)\) is an integer, and \(\mu_t=w_t/Q\). Multiplying the budget inequality by the positive quantity \(dQ^2\) gives exactly
\(d\sum_{(t,u)\in D}w_tw_u\leq cQ^2\).
The comparison remains valid when \(c=0\).
The bit length of \(Q\) is bounded by the total denominator encoding length, hence is \(O(L)\). Positivity and normalization imply \(\mu_t\leq1\), so \(w_t\leq Q\). Summing at most \(\tau^2\) products introduces only \(O(\log(\tau+1))\) additional bits. The input integers \(c,d\) also have \(O(L)\) bits. All arithmetic quantities therefore have the claimed \(O(L)\) bit length.
Computing \(Q\), the \(w_t\), the sum, and the final comparison fits within \(O(\tau^2L^2)\) bit operations using schoolbook arithmetic.
The initial-set scans and graph search correctly compute the specified closure. Empty initial sets and empty target sets require no exceptional mathematical argument; the described procedure handles them. The singleton-support case also satisfies the construction and verification formulas.
The graph computation and target checks fit within the overall \(O(\tau^2L^2)\) bit-operation bound. Membership in \(\mathrm{NP}\), together with the two reductions, proves the claimed \(\mathrm{NP}\)-completeness.
Enumerating all \(2^{\tau^2}\) flip sets gives the stated deterministic bound. The prover appropriately makes no hardness claim for fixed \(|P|\).
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.