Answer: \(\mathrm{NP}\text{-complete}\)
Theorem 0.1 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximate\gmpvr\ is {\rm \npc} on paths.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given \(\tau\) ordered sites, positive rational masses \(\mu_i\) summing to \(1\), candidate set \(C\), per-capita score vectors \(a_i:C\to\mathbb{Z}_{>0}\), target \(p\), and district count \(k\), decide whether indices \(0=i_0<i_1<\cdots<i_k=\tau\) partition the sites into consecutive districts such that \(p\) wins strictly more districts than every rival. Each site’s entire mass must be assigned to one district, and candidate \(c\)’s score in district \(j\) is \(\sum_{i=i_{j-1}+1}^{i_j}\mu_i a_i(c)\); ties count as wins for every tied candidate. The masses are binary encoded; determine the problem’s complexity in \(m\), \(\tau\), and input bit length \(L\).
A society is given by its support: an ordered list of \(\tau\geq1\) site types, each with positive binary rational mass \(\mu_i\), with \(\sum_{i=1}^{\tau}\mu_i=1\). Site identity is part of a type; \(\tau\) is the support size, not the number of possible score vectors.
The input also contains a candidate set \(C\) of size \(m\geq1\), a target \(p\in C\), binary encoded per-capita scores \(a_i:C\to\mathbb Z_{>0}\), and an integer \(1\leq k\leq\tau\). Let \(L\) be the total input bit length.
A feasible partition has integer boundaries \(0=i_0<i_1<\cdots<i_k=\tau\), defining nonempty consecutive districts \(D_j=\{i_{j-1}+1,\ldots,i_j\}\); each site's entire mass belongs to one district.
Define \(S_j(c)=\sum_{i\in D_j}\mu_i a_i(c)\) and \(W_j=\operatorname{argmax}_{c\in C}S_j(c)\). No ties are broken.
The decision problem asks whether a feasible partition satisfies \(\lvert\{j:W_j=\{p\}\}\rvert>\lvert\{j:c\in W_j\}\rvert\) for every \(c\in C\setminus\{p\}\).
Is this decision problem in \(\mathrm P\), or is it \(\mathrm{NP}\)-hard, with running times measured in \(m,\tau,k,L\)?
Discrete weighted single-candidate approval gerrymandering is \(\mathrm{NP}\)-complete on paths, counting only sole victories for the target and counting tied victories for rivals. [Source](https://arxiv.org/pdf/2102.09889v2)
No result settling this exact rational-mass formulation was located.
The decision problem is \(\mathrm{NP}\)-complete. Hardness holds even when every mass is a dyadic rational, meaning an integer divided by a power of two.
The proof preserves each site as an indivisible, separately identified type and preserves every district’s entire winner set, including ties.
We use the known \(\mathrm{NP}\)-completeness of weighted single-candidate approval gerrymandering on paths: Theorem 1.1 of Gupta, Jain, Panolan, Roy, and Saurabh, *Gerrymandering on graphs: Computational complexity and parameterized algorithms*. Their definition counts only sole victories for the target and counts victories either alone or tied for each rival, exactly as required here. See the [definitions and Theorem 1.1](https://arxiv.org/html/2102.09889v2#S1).
A source instance consists of a path with vertices in order \((v_1,\ldots,v_n)\), a candidate set \(C\), a target \(p\), positive integer weights \(w_i\), an approved candidate \(f_i\in C\) for each vertex, and a required number \(k\) of nonempty connected districts. For a district \(D\), its approval total for candidate \(c\) is
\(\displaystyle T_D(c)=\sum_{\substack{i\in D\\f_i=c}}w_i.\)
Its winner set is \(\operatorname{argmax}_{c\in C}T_D(c)\).
We may restrict to \(1\leq k\leq n\): instances with \(k>n\) are automatically no-instances and can be mapped to a fixed no-instance of the target problem.
Given a source instance, retain \(C,p,k\) and create one separately identified site for each vertex, in the same order. Thus \(\tau=n\).
Let \(N\) be the smallest power of two satisfying \(N\geq n\), and put \(r=N-n+1\). Define
\(\displaystyle \mu_i=\begin{cases}1/N,&i<n,\\r/N,&i=n,\end{cases}\qquad t_i=\begin{cases}r,&i<n,\\1,&i=n.\end{cases}\)
These definitions also apply when \(n=1\). Every mass is positive and dyadic, and
\(\displaystyle \sum_{i=1}^{n}\mu_i=\frac{n-1+r}{N}=1,\qquad \mu_i t_i=\frac rN\quad\text{for every }i.\)
Define the positive integer per-capita scores by
\(\displaystyle a_i(c)=t_i\bigl(1+w_i\mathbf 1_{\{f_i=c\}}\bigr).\)
All scores are strictly positive because \(t_i\geq1\).
For any nonempty interval \(D\) and any candidate \(c\), the resulting district score is
\(\displaystyle S_D(c)=\sum_{i\in D}\mu_i a_i(c)=\frac rN\sum_{i\in D}\bigl(1+w_i\mathbf 1_{\{f_i=c\}}\bigr)=\frac rN\bigl(|D|+T_D(c)\bigr).\)
Consequently, for any candidates \(c,d\),
\(\displaystyle S_D(c)-S_D(d)=\frac rN\bigl(T_D(c)-T_D(d)\bigr).\)
Since \(r/N>0\), all strict comparisons and all equalities are preserved. Therefore
\(\displaystyle \operatorname{argmax}_{c\in C}S_D(c)=\operatorname{argmax}_{c\in C}T_D(c).\)
The added baseline makes the scores positive without changing any winner set.
The construction has polynomial encoding length. Indeed, \(N<2n\) and \(1\leq r\leq n\), so the masses and multipliers require \(O(\log(n+1))\) bits each. Every score is at most \(n(1+w_i)\), requiring \(O(\log(n+1)+\log(w_i+1))\) bits. Writing all \(nm\) scores therefore takes polynomial time and space in the source input length.
A nonempty vertex subset induces a connected subgraph of a path precisely when its indices form an interval. To justify the nontrivial direction, if the subset contains \(v_a,v_b\) with \(a<b\), connectivity requires every vertex on the unique path between them, namely \(v_a,\ldots,v_b\).
Thus a partition of the source path into \(k\) nonempty connected districts corresponds exactly, after ordering its districts from left to right, to boundaries
\(\displaystyle 0=i_0<i_1<\cdots<i_k=n.\)
These are precisely the feasible partitions of the constructed society. No vertex or site is split, and sites with identical score vectors remain distinct.
For every corresponding district, the reduction preserves its full winner set. It therefore preserves both the number of sole victories for \(p\) and the number of victories, including tied victories, for each rival. The required strict inequalities hold in the constructed instance if and only if they hold in the source instance.
This proves \(\mathrm{NP}\)-hardness.
A certificate consists of the \(k-1\) internal boundaries, using \(O(k\log(\tau+1))\) bits. Their order and range can be checked in polynomial time.
Exact score verification also takes polynomial time in \(L\). Write each input mass as \(\mu_i=u_i/b_i\), where \(u_i,b_i\) are positive binary integers, and set
\(\displaystyle Q=\prod_{i=1}^{\tau}b_i,\qquad B_i(c)=u_i a_i(c)\frac{Q}{b_i}.\)
Each \(B_i(c)\) is an integer. The bit length of \(Q\) is at most \(1+\sum_i\log_2 b_i\), hence \(O(L)\). Each \(B_i(c)\), and every sum of at most \(\tau\) such integers, likewise has polynomial bit length.
For every certified district \(D_j\),
\(\displaystyle Q S_j(c)=\sum_{i\in D_j}B_i(c).\)
Because \(Q>0\), comparing these integer totals determines the exact winner set \(W_j\). Integer multiplication, division, addition, and comparison on these polynomial-length integers take polynomial time. The verifier then counts the prescribed victories and checks every rival inequality. Hence the problem belongs to \(\mathrm{NP}\).
Together, the reduction and verifier prove \(\mathrm{NP}\)-completeness in the stated binary input model. An algorithm polynomial in \(m,\tau,k,L\) for unrestricted inputs would therefore imply \(\mathrm P=\mathrm{NP}\).
For fixed \(k\), enumerating the \(\binom{\tau-1}{k-1}\) boundary choices and verifying each gives a running time of \(\binom{\tau-1}{k-1}\operatorname{poly}(m,\tau,k,L)\). This restricted tractability is consistent with the hardness when \(k\) is part of the input.
⟨structured verdict parsed — rendered above⟩
The prover’s claim is proved. The reduction preserves the exact decision condition, and the polynomial encoding and verification arguments are valid. No major or minor mathematical issues were found.
The cited theorem applies to the problem described in the write-up. The paper defines GM using positive integer vertex weights, one approved candidate per vertex, and exactly \(k\) nonempty districts whose induced subgraphs are connected. Its success condition counts sole victories for the target and both sole and tied victories for rivals. Theorem 1.1 states that GM is NP-complete on paths. Thus the prover invokes the correct theorem, with the required hypotheses and tie convention. [Source definitions and Theorem 1.1](https://arxiv.org/html/2102.09889v2#S1)
Restricting to \(1\leq k\leq n\) is legitimate: the source already requires positive \(k\), and \(k>n\) cannot admit a partition into nonempty districts. The stated fixed-no-instance handling is routine and does not introduce a substantive gap.
The construction retains the candidate set, target, and district count, and creates precisely one separately identified site per source vertex. Consequently, \(\tau=n\), and coincident score vectors do not collapse distinct sites.
For the smallest power of two \(N\geq n\), the bounds \(N<2n\) and \(1\leq r=N-n+1\leq n\) are correct, including when \(n=1\).
All constructed masses are positive dyadic rationals. The normalization calculation is correct:
\[
\sum_{i=1}^{n}\mu_i=\frac{n-1+r}{N}=1.
\]
The two cases in the definitions also give exactly
\[
\mu_i t_i=\frac rN
\]
for every site.
Because \(t_i\) and \(w_i\) are positive integers, each \(a_i(c)\) is a strictly positive integer. Thus the construction satisfies all mass and score restrictions in USER_TASK.
Substituting the constructed masses and scores yields the stated identity:
\[
S_D(c)=\frac rN\bigl(|D|+T_D(c)\bigr).
\]
There is no omitted candidate-dependent term: the baseline contributes the same quantity \((r/N)|D|\) to every candidate.
The subtraction calculation is therefore correct:
\[
S_D(c)-S_D(d)=\frac rN\bigl(T_D(c)-T_D(d)\bigr).
\]
Since \(r/N>0\), it preserves positive, negative, and zero differences. Consequently, the full argmax set is preserved, including every tie. This establishes the central claim of the reduction without assuming unique district winners.
The path-connectivity argument is valid. A nonempty connected induced vertex subset must contain every vertex between any two of its vertices; hence it is an interval. Conversely, every nonempty interval induces a connected subpath.
Disjoint intervals covering the entire path can be ordered from left to right, giving exactly the required strictly increasing boundaries. Conversely, such boundaries produce a partition into connected nonempty source districts.
The correspondence preserves the district count and never splits a vertex or site. Combined with preservation of winner sets, it preserves both victory counts appearing in every rival inequality. The claimed equivalence of yes-instances follows in both directions.
The mass and multiplier encoding bounds are correct. Although \(N\) may equal \(n\), it always satisfies the claimed strict upper bound \(N<2n\).
Every score satisfies
\[
a_i(c)\leq n(1+w_i),
\]
so its binary length is bounded as stated. Writing the explicit table of \(nm\) scores is polynomial in the explicit source input length: both the vertices and candidate set are part of that input.
The construction therefore establishes polynomial-time many-one hardness, including the claimed restriction to dyadic masses.
The internal boundaries form a polynomial-size certificate. Their number, strict ordering, and range determine whether they describe a feasible partition.
The common-denominator construction is valid even when the input fractions are not reduced. Each denominator divides \(Q\), so every \(B_i(c)\) is an integer.
The bit-length bound for \(Q\) is correct. Each product defining \(B_i(c)\) has polynomial bit length, and summing at most \(\tau\) such integers adds at most a logarithmic bit-length overhead. Thus the integer operations required to compute and compare district totals take polynomial time in the binary input length.
Multiplication by positive \(Q\) preserves all comparisons and ties. The verifier can therefore determine sole target victories and all rival victories exactly, then check the required strict inequalities.
The construction explicitly covers \(n=1\). The arguments also remain valid for \(k=1\), \(k=\tau\), and \(m=1\); in the last case the rival condition is vacuous on both sides.
There are exactly \(\binom{\tau-1}{k-1}\) feasible boundary choices. The claimed enumeration bound is correct and polynomial for each fixed \(k\). It does not contradict NP-completeness when \(k\) varies with the input.
Actionable feedback: No mathematical repair or additional clarification is required. The output resolves USER_TASK in the stated binary encoding model.
⟨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.