| paper | d4-conf-sagt-2023-0025 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
parameterized→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\)-complete and \(\mathrm{W}[2]\)-hard parameterized by \(k\); not FPT unless \(\mathrm{FPT}=\mathrm{W}[2]\). · discrete side: parameterized · adjudication: proved
full proof & adversarial review →
Theorem 3.4
statement extracted from the paper’s text layer
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\).
Types are graph locations paired with their candidate preference, each carrying rational mass \(\mu_v\). Choose a connected district label for each location, assigning each type wholly to one of exactly \(k\) districts; the decision objective is that \(p\)'s number of unique district wins exceed every other candidate's number of district leads.
The mirror covers the unit-weight hardness results in Theorems 3.4 and 4.3. It leaves the weighted algorithm in Theorem 5.3 and Corollary 5.4 unmirrored.
The strongest mirror I believe is Mass Gerrymandering on depth-two trees. A type is a precinct-like location together with its candidate preference: \(t_v=(v,\chi(v))\). Residents of that type share the same location, preference, and role in the graph, so they are indistinguishable for this problem. The society is a distribution \(\mu\) over the graph’s vertices, with each \(\mu_v\in\mathbb{Q}_{>0}\) and \(\sum_v\mu_v=1\). The regime is a large electorate concentrated in a comparatively small number \(\tau\) of homogeneous, connected localities. For example, each of \(\tau\) precincts could contain \(R\) residents of the same affiliation, so the population is \(N=R\tau\) while the input lists only \(\tau\) types.
Here is the continuous decision problem. Given a tree \(G=(V,E)\), candidate set \(C\), preference map \(\chi:V\to C\), target \(p\), district count \(k\), and the binary-rational masses \(\mu_v\), partition \(V\) into exactly \(k\) nonempty connected sets \(D_1,\dots,D_k\). In district \(D\), candidate \(c\)’s support is
\[
s_D(c)=\sum_{v\in D:\chi(v)=c}\mu_v.
\]
A candidate leads a district if they attain its maximum support; \(p\) wins a district if \(p\) is its unique leader. The question is whether some partition lets \(p\) win more districts than any other candidate leads. A solution is the connected district partition. Each locality type is assigned as a whole, as in the paper’s graph model.
The lead anchor is Theorem 3.4, proved in this paper by reduction from Set Cover: *Unit Weight Gerrymandering is W[2]-hard on trees of depth two when parameterized by the number of districts \(k\).* Its continuous counterpart is Mass Gerrymandering restricted to depth-two trees; I expect the same W[2]-hardness with parameter \(k\). Every unit-weight instance maps to one with \(\mu_v=1/|V|\), which preserves every district comparison. Thus a fixed-parameter algorithm in \(k\), with polynomial dependence on \(|C|\), \(\tau\), and the mass bit length \(L\), would also solve the paper’s instances.
A second anchor worth keeping is Theorem 4.3, also proved here by reduction from Set Cover: *Unit Weight Gerrymandering remains W[2]-hard on subdivided stars with \(\ell\) leaves, parameterized by \(k+\ell\).* The corresponding continuous question is the same mass-partition problem restricted to subdivided stars, with parameter \(k+\ell\); I again expect hardness to transfer. This result captures a different regime from Theorem 3.4: hardness persists even on a very simple tree shape when the combined district and leaf parameters vary. It does not claim hardness for a fixed \(\ell\).
These mirrors preserve the authors’ problem rather than replacing it with a simpler voting question: the graph, connectedness requirement, district count, plurality comparison, and indivisibility of graph vertices all remain. What changes is how an electorate attached to each locality is represented. The unit-weight instances embed exactly by normalization, and cloning every voter at a locality leaves the mass input and district outcomes unchanged. The expected classification is therefore hardness transfers (Class B): the reduction’s combinatorics live in choosing connected districts and in the candidate structure, not in the granularity of individual voter counts.
My weakest point is also the main modeling choice: this makes the *electorate* continuous while retaining indivisible localities. It does not let a district split one locality’s mass across multiple districts. I think that is defensible because indivisible vertices are part of the paper’s graph model, and precinct-like areas are often assigned as units. If the intended mirror instead requires fractional allocation within every vertex, that would be a different geographic model and the hardness transfer would need a new argument. The paper’s reductions also use an unbounded candidate set, so these anchors do not establish hardness for two-candidate elections.
The immediate follow-up questions are whether either hardness result survives when \(|C|\) is fixed, and what changes if a richer geographic model permits splitting locality mass while preserving district connectivity. This case covers the paper’s two unit-weight hardness theorems; it does not claim to mirror the weighted algorithm in Theorem 5.3 or Corollary 5.4.
The strongest objection is that both hardness results are about assigning graph vertices to districts. The vertices are the indivisible units: each must belong wholly to one connected district. Their positions in the tree are part of what makes them distinct, so a natural voter type has to include location as well as preference. That makes the support size \(\tau\) essentially the number of graph vertices. Increasing the population at a vertex does not add a new choice to the districting problem.
The most plausible mass version assigns each vertex a rational population share \(\mu_v\), then compares candidates by the mass of their supporters in each district. But this changes only the vote totals. Multiplying all the rational shares by a common denominator gives integer vote counts with exactly the same winners for every district partition. The result is a weighted graph districting problem on the same tree. That is a sensible high multiplicity interpretation, but it supplies no new continuous decision structure: there is no mass transfer, fractional assignment, or optimization over a continuum of districts. The relevant computation remains over connected partitions of the graph.
That objection applies to Theorem 3.4 and Theorem 4.3 alike. Their reductions use unit votes at graph vertices; normalizing those votes preserves the reductions exactly. In Theorem 4.3, the leaf count \(\ell\) is also a property of the graph, so representing residents as mass does not change the structure responsible for the \(k+\ell\) parameter. This is not an argument that transferring hardness would be uninteresting. It is that, for these anchors, the transfer comes from rescaling vertex weights, without changing the computational object.
A richer proposal would let residents at one vertex be divided among districts. But the paper’s graph records adjacency between whole vertices; it says nothing about how to split a vertex’s territory or maintain connectedness after a split. Allowing its mass in several districts would make districts overlap at that location. A nonoverlapping geographic version would need finer spatial structure absent from the model. So the more genuinely continuous version requires a new districting model, not just a better choice of types or masses.
This negative case has a real limit: precincts or localities with many homogeneous residents, assigned whole, are a plausible high multiplicity regime, and the authors might recognize the rational mass formulation as their problem. The case against is that this regime appears to make Gerrymandering a weighted graph problem rather than expose the kind of continuous population computation ChoCo is looking for. I cannot rule out that the weighted problem is worth studying; I can only argue that these two theorems provide weak anchors for a continuous mirror.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.