d4-conf-sagt-2021-0023

My lead is Atomic Continuum Path Gerrymandering (ACPG), mirroring Theorem 0.1. That theorem says that \(\mathrm{GM}_{\mathrm{PVR}}\) is NP-complete on paths: given a path of voters, candidates, positive integer candidate weights for each voter, a target \(p\), and a district count \(k\), decide whether the path’s vertices can be partitioned into \(k\) connected districts so that \(p\) wins more districts than every other candidate. Count a candidate as winning a district whenever it is among that district’s winners, including ties. The paper proves this theorem with a reduction from Rainbow Matching on paths; it cites the NP-completeness of that source problem.

For ACPG, the input is an ordered set of rational positions \(x_1<\cdots<x_\tau\) on a line, a candidate set \(C\), a target \(p\in C\), and \(k\). At each position \(x_i\) is a positive rational mass \(\mu_i\), with \(\sum_i\mu_i=1\), of residents sharing a per-capita score vector \(a_i:C\to\mathbb Z_{>0}\). The complete type is \(t_i=(x_i,a_i)\): location matters because it determines which districts are connected. A district is an interval, and all mass at a support position must go to the same district. Equivalently, a solution is a sequence of cuts \(0=i_0<i_1<\cdots<i_k=\tau\), assigning the consecutive support points \(i_{j-1}+1,\ldots,i_j\) to district \(j\). Its score for candidate \(c\) is
\[ \mathrm{sc}_j(c)=\sum_{i=i_{j-1}+1}^{i_j}\mu_i a_i(c). \]
The question is whether some cut sequence makes \(p\) win more districts than every rival. The decision variable is the cut sequence; the objective is feasibility. Masses and positions are encoded as binary rationals, so running time is measured in \(m\), \(\tau\), and input bit length \(L\).

A plausible regime is precinct-preserving redistricting along a corridor: each precinct contains many residents with the same score vector, precincts form a path, and districts must contain whole precincts. If there are \(B\) residents per precinct, the population is \(N=B\tau\) while the support has only \(\tau\) complete location-preference types. This is a high-multiplicity population: mass represents the cohort at each site, while geography keeps that cohort together.

The match to the theorem is exact. Given its path instance, put one support point at each voter vertex, set \(\mu_i=1/\tau\), and take \(a_i(c)=w_{v_i}(c)\). Every connected district of a path is a consecutive block, just as every ACPG district is. Each district’s ACPG scores are the original scores multiplied by \(1/\tau\), so its winner set is unchanged. Thus the partitions correspond exactly, and ACPG is NP-hard even on this equal-mass subfamily. ACPG is also in NP: a cut sequence is a polynomial-size certificate, and its rational scores can be compared in polynomial time. The expected classification is therefore hardness transfers: ACPG is NP-complete.

I think the authors would recognize this as their problem with precinct cohorts in place of individual voters: the score aggregation, connected districts, and target-winner condition all remain. This mirror covers Theorem 0.1 specifically; it makes no claim about continuous versions on general graphs or about the paper’s algorithmic results.

The weak point is that the mirror’s exactness relies on whole-precinct assignment. If the intended continuous model allows a cut to split the mass at a location, Theorem 0.1 no longer proves hardness for that different problem. A natural next question is whether the nonatomic version, with positive density that cuts can divide, remains hard or becomes tractable under continuous optimization.