| paper | Gerrymandering Planar Graphs |
| authors | — |
| venue | AAMAS 2024 |
| filed under | voting · bribery-control |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 3.3
statement extracted from the paper’s text layer
Given a planar graph \(G=(V,E)\), candidates \(C\), target \(b\in C\), approval map \(a:V\to C\), integer \(k\), and rational masses \(\mu_v>0\) with \(\sum_{v\in V}\mu_v=1\), does there exist a partition \(V=D_1\mathbin{\dot\cup}\cdots\mathbin{\dot\cup}D_k\) into nonempty connected districts such that for some \(D_i\), \(\sum_{v\in D_i:a(v)=b}\mu_v>\sum_{v\in D_i:a(v)=c}\mu_v\) for every \(c\in C\setminus\{b\}\)?
The society is a distribution \(\mu\) over location-approval types \(t_v=(v,a(v))\). The masses are fixed population fractions, while decision variables are indivisible connected districts; the objective is to decide whether at least one district is won by \(b\), or to maximize the number of districts won.
The mirror covers Theorem 3.3 and Corollary 3.4, including one-winning-district decision and seat-maximization inapproximability. It leaves the bounded-treewidth algorithms, the planar approximation results, and the singleton-winning-district PTAS outside its scope.
The strongest honest case is a direct, Class-B mirror anchored by Theorem 3.3. I would not claim that continuization makes this problem tractable; the point is that it gives a faithful high-multiplicity problem whose hardness survives because the real combinatorics lie in planar connectivity.
Take an instance
\[
I=(G=(V,E),C,b,k,a,\mu),
\]
where \(G\) is a planar county-adjacency graph, \(C\) is the candidate set, \(b\in C\) is the gerrymanderer’s candidate, \(a:V\to C\) gives the candidate approved by residents of county \(v\), and \(\mu_v\in\mathbb{Q}_{>0}\) is the fraction of the electorate living in \(v\), with \(\sum_{v\in V}\mu_v=1\).
The voter type is \(t_v=(v,a(v))\): location is part of the type because it affects connectivity, while approval is the electoral attribute. A large population consists of many exchangeable residents of each county type. The action is still a partition of the counties, not a fractional assignment of residents:
\[
V=D_1\mathbin{\dot\cup}\cdots\mathbin{\dot\cup}D_k,
\]
with every \(D_i\) nonempty and connected in \(G\). Define
\[
M_i(c)=\sum_{\substack{v\in D_i\\a(v)=c}}\mu_v.
\]
The continuous problem, which I would call \(\mathrm{OneWin\text{-}Gerry}^{\infty}_{\mathrm{planar}}\), asks whether there is such a partition and some district \(D_i\) satisfying
\[
M_i(b)>M_i(c)\qquad\text{for every }c\in C\setminus\{b\}.
\]
A solution is the partition itself.
This is a credible high-multiplicity regime for a large municipal or regional election: the map has perhaps hundreds or thousands of county or census-unit types, while each type contains many residents who are indistinguishable for the districting problem. Thus \(N\gg \tau\), where \(N\) is the number of residents and \(\tau=|V|\) is the number of location-approval types. The paper already assigns each vertex a voting weight, so replacing integer vote counts by population fractions is exactly the natural normalization of its model.
The lead anchor is Theorem 3.3, proved in this paper in Section 3.2. It states that “for planar graphs, finding a partition with one winning district is NP-hard.” The proof reduces from minimum connected vertex cover and forces any winning district to encode a connected vertex cover. That source of difficulty is the planar graph’s connectivity structure and the candidate-color gadgetry, not the individuality of voters.
The rational-clone correspondence is exact. If \(\mu_v=p_v/Q\), create \(p_v\) cloned voters of type \(t_v\). For any district and candidate, its mass is exactly its clone vote count divided by \(Q\), so all strict winner comparisons are preserved. Conversely, a finite weighted instance with vertex weights \(w(v)\) gives
\[
\mu_v=\frac{w(v)}{\sum_{u\in V}w(u)}.
\]
In particular, the hard instances of Theorem 3.3 already transfer using uniform masses \(\mu_v=1/|V|\). Therefore an algorithm for \(\mathrm{OneWin\text{-}Gerry}^{\infty}_{\mathrm{planar}}\) would solve the paper’s NP-hard instances. I expect this mirror to be Class B: hardness transfers unchanged.
The same normalization also carries the paper’s Corollary 3.4 to the associated optimization problem, where the objective is
\[
\max_D\left|\{i:b\text{ wins }D_i\}\right|.
\]
A finite-factor approximation would have to find a winning district whenever one exists, contradicting Theorem 3.3 unless \(P=NP\).
The authors should recognize this as their problem rather than as a softened substitute. It preserves the planar map, indivisible counties, connected districts, candidate approvals, strict winner convention, district count, and seat-maximization objective. Only the number of residents represented by each county changes from an integer count to a normalized mass. Continuizing the geography or allowing a county’s population to be split between districts would be a different extension, not the direct mirror.
This mirror generates useful further questions. Is the one-winning-district problem polynomial for a fixed number of candidates, as the paper itself asks? Does allowing arbitrary rational masses create new threshold phenomena when winning margins become very small? Can the optimization problem admit approximation under bounded candidate count or a sufficiently large optimum? And what is the correct model, and complexity classification, if one genuinely allows district boundaries to cut through continuous geographic population rather than preserving whole counties?
The weakest point is that \(\mu\) affects district scores but not the feasible partition: the mirror is therefore a weighted high-multiplicity restatement, not a new fractional districting model. If the programme required the action variable itself to be continuous, this case would fail. But that requirement would continuize the administrative units or outcomes, whereas ChoCo’s stated scope is the population. On that scope, this is a legitimate and author-recognizable mirror whose main result is precisely that population continuity does not dissolve hardness driven by planar connectivity.
I would not claim that Theorems 2.1 or 2.2 yield a polynomial-time algorithm for arbitrary rational masses: their running time depends pseudo-polynomially on total integer vertex weight, and the paper explicitly says that dependence is necessary. Nor would I use the unweighted approximation results as primary anchors. The clean case is narrower: Theorem 3.3, with Corollary 3.4 as its immediate optimization consequence.
The strongest case against the proposed mirror is semantic rather than complexity-theoretic. With county boundaries preserved, replacing \(w(v)\in\mathbb{N}\) by rational masses \(\mu_v\) is essentially a change of units. For a common denominator \(Q\), setting \(w(v)=Q\mu_v\) preserves every district comparison and therefore every feasible partition. The paper already permits weighted vertices, and its hard instances in Theorem 3.3 are unweighted. Thus the continuous population plays no role in the reduction: all the combinatorics remain in the indivisible graph.
The proposed type \(t_v=(v,a(v))\) also exposes the limitation. Location must be part of the type because it determines connectivity, so there is effectively one relevant type per county. The many residents of a county are exchangeable clones, but none can be acted on separately: the decision variable still partitions counties. This is a high-multiplicity encoding of a weighted graph problem, not a population-level computational relaxation. A more genuinely continuous model would use a density over a geographic domain and allow district boundaries to cut through population. But that is a new geometric partition problem. Thin corridors could connect regions at arbitrarily small population mass, and without additional regularity or minimum-width constraints the discrete connectivity gadgetry may disappear.
That is the best available attack, but it does not defeat the anchor under ChoCo’s stated rules. High multiplicity is explicitly allowed to preserve indivisible administrative units while replacing individual counts by population fractions. A large county cohort is a perfectly intelligible type, and the fact that the action remains a county partition is not disqualifying: the programme continuizes the society, not necessarily the intervention. Nor is exact equivalence to cloned voters an objection; it is precisely the required high-multiplicity bridge.
Indeed, Theorem 3.3 transfers exactly. For every rational \(\mu\), clearing denominators gives the corresponding weighted instance, and for the paper’s reduction one may simply use \(\mu_v=1/|V|\). Strict plurality comparisons are unchanged. The same is true of Corollary 3.4: maximizing the number of districts won by \(b\) has the identical objective, so a finite-factor approximation would still have to detect whether the optimum is zero or positive. This is a legitimate Class-B result, and the programme explicitly treats such mirrors as worthwhile even when continuity does not remove the hardness.
Allowing heterogeneous approval masses \(\mu_{v,c}\), or allowing a continuous geographic population density, would produce richer questions, but their novelty does not undermine the simpler mirror. They are extensions rather than reasons that the direct mirror is invalid.
So the honest negative case is weak. One can criticize the proposed construction as a weighted high-multiplicity restatement with limited conceptual novelty, and insist that a genuinely geometric continuum needs separate modelling. But one cannot credibly claim that no worthwhile continuous mirror exists: Theorem 3.3, and consequently Corollary 3.4, survive as sensible population-continuous computational problems.
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.