Answer: \(\mathrm{NP}\)-complete and \(\mathrm{W}[2]\)-hard parameterized by \(k\); not FPT unless \(\mathrm{FPT}=\mathrm{W}[2]\).
Theorem 3.4 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateUnit Weight Gerrymandering is W[2]-hard in trees of depth 2 when parameterized by the number of districts k.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a depth-two tree \(G=(V,E)\), candidates \(C\), a preference map \(\chi:V\to C\), target \(p\), district count \(k\), and positive rational masses \(\mu_v\) summing to \(1\), decide whether \(V\) can be partitioned into exactly \(k\) nonempty connected districts such that \(p\) uniquely leads more districts than any other candidate leads. Each vertex’s mass is assigned wholly to its district; in district \(D\), candidate \(c\)'s support is \(\sum_{v\in D:\chi(v)=c}\mu_v\).
Input: a finite simple undirected tree \(G=(V,E)\) with a specified root whose maximum distance to a vertex is \(2\), candidates \(C\) with \(m=|C|\geq2\), a preference map \(\chi:V\to C\), a target \(p\in C\), and an integer \(1\leq k\leq |V|\).
A society is given by its support: the list of its \(\tau\) types with positive mass, each mass a binary rational. Here types are distinct geographical vertices, including their candidate preferences; \(\tau=|V|\) is the support size, not the number of possible types. Masses satisfy \(\mu_v>0\) and \(\sum_{v\in V}\mu_v=1\). Let \(L\) be the total binary input length; state running times in \(m,\tau,L,k\).
A feasible partition consists of exactly \(k\) nonempty districts \(\mathcal D\), each inducing a connected subgraph. Each vertex and its entire mass belong to one district; there are no district population constraints.
For a district \(D\), define \(s_c(D)=\sum_{v\in D:\chi(v)=c}\mu_v\) and \(T(D)=\operatorname*{arg\,max}_{c\in C}s_c(D)\). Every member of \(T(D)\) leads; a candidate wins only when it is the sole member. Ties are not broken.
The decision problem asks whether such a partition satisfies \(|\{D\in\mathcal D:T(D)=\{p\}\}|>|\{D\in\mathcal D:c\in T(D)\}|\) for every \(c\in C\setminus\{p\}\).
Is this decision problem in \(\mathrm P\), or is it NP-hard?
If it is NP-hard, is it FPT parameterized by \(k\)?
Nearest known results: unit-weight Gerrymandering on depth-two trees is \(\mathrm{W}[2]\)-hard parameterized by \(k\) ([Fraser–Lavallee–Sullivan](https://arxiv.org/html/2205.06857v2)).
With positive integer vertex weights and the same district and tie conditions, Gerrymandering is strongly NP-complete on trees of diameter four ([Ito–Kamiyama–Kobayashi–Okamoto](https://www.ifaamas.org/Proceedings/aamas2019/pdfs/p1413.pdf)). No separately stated result for normalized rational masses was verified.
The problem is \(\mathrm{NP}\)-complete and \(\mathrm{W}[2]\)-hard parameterized by \(k\). Consequently, it is not FPT parameterized by \(k\) unless \(\mathrm{FPT}=\mathrm{W}[2]\).
Here “binary rational” means an exact rational whose numerator and denominator are encoded in binary. This is the usual rational input model; it does not require a finite binary expansion.
Consider an instance with positive integer vertex weights \(w_v\). Define
\(W=\sum_{v\in V}w_v\) and \(\mu_v=w_v/W\).
All masses are positive and sum to one. The graph, its vertices, their preferences, the candidates, and \(k\) remain unchanged. In particular, the support size remains \(\tau=|V|\).
For every nonempty district \(D\) and candidate \(c\),
\(s_c(D)=W^{-1}\sum_{v\in D:\chi(v)=c}w_v\).
Multiplication by the positive constant \(W^{-1}\) preserves strict inequalities and equalities. Therefore the entire set \(T(D)\) is unchanged. This preserves both the number of districts that \(p\) wins alone and the number that each opponent leads, including tied districts.
The transformation has polynomial output length. If every input weight has at most \(b\) bits, then \(W<\tau 2^b\), so its binary length is at most \(b+\lceil\log_2\tau\rceil+1\). Each output mass therefore uses \(O(b+\log\tau)\) bits. Computing \(W\) and writing these fractions takes polynomial time; reducing the fractions, if required by the encoding, also takes polynomial time.
Thus normalization is a polynomial-time reduction that preserves \(k\) exactly.
Theorem 3.3 of Ito–Kamiyama–Kobayashi–Okamoto states that integer-weight Gerrymandering is strongly \(\mathrm{NP}\)-complete on trees of diameter four. Its definition requires exactly \(k\) nonempty connected districts and compares \(p\)'s sole victories against every opponent's appearances among the district leaders. Its vertex weights are positive integers. These are precisely the district and tie conditions in the question. [Source: definitions in Section 2 and Theorem 3.3](https://www.ifaamas.org/Proceedings/aamas2019/pdfs/p1413.pdf).
A diameter-four tree can be rooted with maximum root distance exactly two. For completeness, take a diameter path \(x_0,x_1,x_2,x_3,x_4\) and root at \(x_2\). For any vertex \(v\), let its path to this diameter path first meet it at \(x_i\), and put \(h=\operatorname{dist}(v,x_i)\). Since neither endpoint can be farther than four from \(v\),
\(h+i\leq4\) and \(h+4-i\leq4\).
Hence \(h\leq\min(i,4-i)\), and
\(\operatorname{dist}(v,x_2)=h+|i-2|\leq2\).
The endpoints attain distance two. Finding this root takes polynomial time.
Apply the normalization from Section 1 to the cited hard instances and specify this root. Every resulting instance satisfies the required positivity, normalization, support, and depth conditions, and has exactly the same successful partitions. This proves \(\mathrm{NP}\)-hardness.
Write each mass as \(\mu_v=a_v/b_v\), with positive binary integers \(a_v,b_v\). Define
\(Q=\prod_{v\in V}b_v\) and \(A_v=a_v(Q/b_v)\).
Then \(\mu_v=A_v/Q\).
Because \(L\) includes all numerator and denominator encodings, \(Q\) has \(O(L)\) bits. The validity condition \(\mu_v\leq1\) implies \(A_v\leq Q\). Moreover,
\(\sum_{v\in V}A_v=Q\),
so every district score computed using the integer weights \(A_v\) also has \(O(L)\) bits. These integer scores preserve every leader set exactly.
A certificate assigns each vertex a district index in \(\{1,\ldots,k\}\). Its length is \(O(\tau\log(k+1))\). Verification proceeds as follows:
Using ordinary integer arithmetic, a conservative bound for preprocessing and verification is
\(O((\tau+mk+1)(L+1)^2)\) bit operations. In particular, verification is polynomial in the total binary input length. Therefore the problem belongs to \(\mathrm{NP}\), and Section 2 proves that it is \(\mathrm{NP}\)-complete.
Theorem 3.4 of Fraser–Lavallee–Sullivan proves that Unit Weight Gerrymandering is \(\mathrm{W}[2]\)-hard parameterized by the number of districts on depth-two trees. Their formal definition counts sole victories for \(p\) against all districts led by each opponent. The construction supplies a root of maximum distance exactly two, has multiple candidates, and uses \(k=t+3\), where \(t\) is the source Set Cover parameter. [Source: Section 2, Definition 3.2, and Theorem 3.4](https://arxiv.org/html/2205.06857v2).
For each such unit-weight instance, assign every vertex the mass \(\mu_v=1/\tau\). By Section 1, this preserves every leader set and the answer. It preserves \(k\), and the mass list uses \(O(\tau\log(\tau+1))\) bits.
Composing this polynomial, parameter-preserving normalization with the cited parameterized reduction proves \(\mathrm{W}[2]\)-hardness for the present problem, even when all masses are equal.
An FPT algorithm here would have running time
\(f(k)(m+\tau+L)^{O(1)}\)
for some computable function \(f\), with a constant exponent independent of \(k\). Such an algorithm would make the cited \(\mathrm{W}[2]\)-hard problem FPT and imply \(\mathrm{FPT}=\mathrm{W}[2]\). Thus the negative FPT conclusion is conditional on the standard separation assumption.
Every partition of a tree into exactly \(k\) connected districts corresponds to deleting exactly \(k-1\) edges.
Indeed, the induced tree on a district \(D\) contains \(|D|-1\) edges. Summing over the districts gives \(\tau-k\) internal edges. Since the tree has \(\tau-1\) edges, exactly \(k-1\) edges cross between districts. Deleting those edges yields precisely the districts. Conversely, deleting \(k-1\) edges from a tree produces exactly \(k\) nonempty connected components.
Enumerate all \(\binom{\tau-1}{k-1}\) deletion sets and verify their component partitions by Section 3. A conservative total running time is
\(O\!\left(\left[1+\binom{\tau-1}{k-1}\right](\tau+mk+1)(L+1)^2\right)\).
Since \(\binom{\tau-1}{k-1}\leq\tau^{k-1}\), this is an XP algorithm parameterized by \(k\), and is polynomial for every fixed \(k\). It does not provide an FPT bound because its exponent depends on \(k\).
⟨structured verdict parsed — rendered above⟩
The prover resolves the task correctly: the problem is \(\mathrm{NP}\)-complete and \(\mathrm{W}[2]\)-hard parameterized by \(k\), so it is not FPT unless \(\mathrm{FPT}=\mathrm{W}[2]\). I found no major or minor mathematical issues.
The prover explicitly adopts the standard encoding of a rational by a binary numerator and denominator. This is a natural interpretation of the task, and the normalization uses this interpretation consistently.
Since every \(w_v>0\), the total \(W\) is positive, every \(\mu_v=w_v/W\) is positive, and their sum is one. The displayed score identity is correct for every district and candidate, including candidates with zero score. Scaling all scores by the same positive factor preserves every equality and strict inequality, hence the complete leader set. Both sides of every required electoral inequality are consequently preserved.
No vertex is split, removed, or merged. Thus connectivity, nonemptiness, district count, preferences, and support size are preserved.
The output-length estimate is valid: \(w_v<2^b\) gives \(W<\tau 2^b\), and each fraction has \(O(b+\log\tau)\) bits. Computing the sum and optionally reducing fractions takes polynomial time. The reduction preserves \(k\) exactly.
Theorem 3.3 does state strong \(\mathrm{NP}\)-completeness for trees of diameter four. Section 2 specifies positive integer weights, exactly \(k\) nonempty connected parts, and precisely the comparison of \(p\)'s sole victories against every opponent's leader appearances. The construction also has multiple candidates. Thus the cited theorem applies to the claimed source problem. [Ito–Kamiyama–Kobayashi–Okamoto, Section 2 and Theorem 3.3](https://www.ifaamas.org/Proceedings/aamas2019/pdfs/p1413.pdf).
The rooting calculation is correct. In a tree, the attachment point \(x_i\) is unique, and the paths to the diameter endpoints give the stated distances. The two inequalities imply \(h\leq\min(i,4-i)\). For every index \(i\) on this path, the displayed bound \(h+|i-2|\leq2\) follows. Both endpoints have distance two from \(x_2\), so the maximum root distance is exactly two.
Finding a diameter path and its middle vertex is polynomial time. Combining rooting with normalization therefore produces valid target instances and preserves the answer in both directions. The \(\mathrm{NP}\)-hardness conclusion follows.
The common denominator \(Q\) has \(O(L)\) bits because its binary logarithm is bounded by the sum of the denominator encoding lengths. Each \(Q/b_v\) is an integer, so every \(A_v\) is computed exactly.
The bounds \(A_v\leq Q\) and \(\sum_v A_v=Q\) follow from the promised mass conditions. Every district score is a nonnegative partial sum and therefore at most \(Q\). Thus the arithmetic operands and scores have \(O(L)\) bits.
The certificate size is polynomial, including when \(k=1\). Checking nonempty districts and connectivity, computing scores, recording all tied leaders, and checking every opponent implements the decision condition exactly. Opponents absent from all preferences are handled by their zero scores; nonempty districts have positive total mass.
The stated conservative bound \(O((\tau+mk+1)(L+1)^2)\) accommodates ordinary multiplication and division, score accumulation, connectivity checks, and candidate comparisons. It is polynomial under the explicit input encoding. Together with hardness, this establishes \(\mathrm{NP}\)-completeness.
Theorem 3.4 in the specified version states \(\mathrm{W}[2]\)-hardness for unit-weight Gerrymandering on depth-two trees, parameterized by district count. The definitions match the task's sole-win and tied-leader distinction. Definition 3.2 supplies \(k=t+3\), multiple candidates, and a root with branches reaching distance exactly two. [Fraser–Lavallee–Sullivan, Section 2, Definition 3.2, and Theorem 3.4](https://arxiv.org/html/2205.06857v2).
Assigning mass \(1/\tau\) is precisely the normalization already verified. Its output length is \(O(\tau\log(\tau+1))\), and it preserves \(k\). Hence composition transfers the cited parameterized hardness, even to equal masses.
The FPT implication is correctly conditional. An algorithm with running time \(f(k)(m+\tau+L)^{O(1)}\) would yield an FPT algorithm for the cited hard problem. The output does not claim an unconditional separation.
Each district induces a tree and has \(|D|-1\) internal edges. Summing gives \(\tau-k\), leaving exactly \(k-1\) crossing edges. Deleting these yields precisely the districts. Conversely, deleting \(k-1\) tree edges creates exactly \(k\) nonempty connected components.
The enumeration count and total running-time bound are valid. For \(k=1\), the sole deletion set is empty; for \(k=\tau\), it contains all edges. Both cases are covered. The inequality \(\binom{\tau-1}{k-1}\leq\tau^{k-1}\) establishes the claimed XP bound.
No repair or additional clarification 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.