| paper | d4-conf-atal-2017-0267 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
NP-hard→P discrete result → its continuous mirror
Answer: polynomial-time solvable · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
Given a planar cell graph \(H=(P,F)\), three alternatives \(C=\{a_1,a_2,a_3\}\), rational masses \(\mu_{v,a}\ge 0\) for singleton-approval types with \(\sum_{v,a}\mu_{v,a}=1\), and a rational threshold \(q\), do there exist two representatives \(r_1,r_2\in C\) (repetitions allowed) and allocations \(x_{v,a,j}\ge 0\), with \(\sum_{j=1}^{2}x_{v,a,j}=\mu_{v,a}\), such that each district has nonempty connected positive-mass support and \(\sum_{v,a,j}x_{v,a,j}\mathbf{1}[r_j=a]\ge q\)?
Types are cell-and-approval pairs \((v,\{a\})\) with rational mass \(\mu_{v,a}\) on a planar graph \(H\). Choose two representatives, allowing repetition, and allocate each type’s mass between them; each district’s positive-mass cell support must be connected, and the objective is total approval satisfaction.
Arbitrarily small connector shares make connectivity irrelevant to the score’s supremum and can leave the maximum unattained, limiting the mirror’s substantive connectivity question to exact attainment.
fatal: False
The main mirror uses Theorem 1’s planar, two-district, three-alternative, singleton-approval restrictions for the non-unique variant. Theorem 2’s path case and Theorem 3’s tree algorithm are separate proposed extensions; Theorems 4–5 and other variants are not covered.
The strongest mirror I see is a mass version of Approval SPR for large, coarse-grained networks. The paper already motivates SPR with customers who approve products and connected shipping areas. Take a large city or region with many customers but a modest number of neighborhood cells. A type is \((v,S)\): a customer’s network cell \(v\) and approved product set \(S\). Customers of the same type have the same preferences and network role. Thus \(N\), the number of people, can be much larger than the number \(\tau\) of positive-mass types.
Let \(H=(P,F)\) be the graph of neighborhood cells, and let \(\mu_{v,S}\) be the rational fraction of the population of each type. For \(k\) districts, choose representatives \(a_1,\ldots,a_k\) and masses \(x_{v,S,j}\geq 0\), with \(\sum_j x_{v,S,j}=\mu_{v,S}\). District \(j\)’s support is the set of cells receiving positive mass for it; require that support to be connected in \(H\). Its satisfaction is
\[ \sum_{v,S} x_{v,S,j}\mathbf{1}[a_j\in S], \]
and the objective is to maximize total satisfaction. The unique variant requires distinct representatives; the non-unique variant permits repeats. Every person still gets one representative—the fractional quantities describe how much of each indistinguishable cohort goes to each district.
My lead is a continuous mirror of Theorem 1. Theorem 1, proved in this paper by reduction from planar 2-Disjoint Connected Subgraphs, says SPR is NP-hard even when the graph is planar, there are three alternatives, \(k=2\), and every voter approves exactly one alternative. The paper says this hardness holds for both unique and non-unique SPR; the hardness of the source problem is cited from [30].
Call the mass version with those same restrictions Planar Singleton-Approval Mass SPR. Its input is a planar cell graph \(H\), rational masses \(\mu_{v,\{a\}}\) for three alternatives \(a\), and a rational target \(q\). It asks whether two connected districts can receive all the mass and achieve satisfaction at least \(q\), with either distinct representatives or unrestricted repeats. A solution is the representatives and the mass assignment \(x\) satisfying the constraints above. This is recognizably the paper’s problem: choose products and partition customers into connected, satisfied shipping areas. The continuous question is whether the hard connected-network choice remains hard when each cell contains divisible mass.
I would initially expect this problem to be hard for continuum-specific reasons (Class C). The planar connectivity choices carry substantial combinatorics even when the population inside each cell is large. But Theorem 1 does not prove that conclusion: splitting a cell’s mass can let two districts use the same cell as a connector, which the discrete reduction does not allow. A reduction that survives that possibility is exactly the work the mirror invites.
A second, narrower question mirrors Theorem 2. That theorem, also proved here, says the unique variant is NP-hard on path graphs for 2-Approval. Its proof reduces from Convex Recoloring on paths, whose hardness is cited from [21]. The continuous mirror, Path Unique 2-Approval Mass SPR, takes a path \(H\), rational masses over cells and approval sets of size two, a district count \(k\), and a target \(q\). It asks for a mass assignment to \(k\) connected districts with pairwise distinct representatives and satisfaction at least \(q\). This preserves the paper’s unique-representative question while replacing individual counts by cohort proportions. My expectation is again hard, provisionally Class C: the order of the cells and the distinct-representative constraint remain, but fractionally splitting cohorts might erase the reduction’s hardness.
Theorem 1 is the stronger anchor: its planar setting and singleton approvals make the continuous decision problem especially direct, and its network hardness fits the programme’s aim of testing whether population continuization removes discrete hardness. Theorem 2 adds a useful challenge on paths, where connectivity is simpler but uniqueness still matters. This scope covers only these hard Approval-SPR results; it does not claim to mirror the whole paper.
The weakest point is that connectivity belongs to individual voters’ network positions, so aggregation is convincing only in a regime with real repeated structure. The neighborhood model supplies that structure, but it coarsens the graph and permits mass splitting within a cell. The authors could reasonably ask whether that is still their SPR problem. The commercial scenario makes the case: connected shipping regions and product satisfaction are already their example, and large cohorts with shared preferences and network roles are a plausible instance of it.
That soft spot also generates the key follow-up questions: does the mass optimum converge to the optimum on large finite expansions of the cell types, and with what additive error? Can the discrete hardness reductions be made robust to split mass? As a tractability boundary, does the paper’s Theorem 3—non-unique SPR is polynomial-time solvable on trees, proved here by dynamic programming—extend to this mass-splittable model? Those questions make this a meaningful continuous computational programme even before their answers are known.
The paper does have computational results to mirror: Theorems 1 and 2 are clear anchors. My strongest case against them is that SPR’s central constraint—each district must be connected—depends on indivisible voters in a way that a mass relaxation handles poorly.
Take the proposed cell graph \(H\), assume it is connected, and let each populated cell \(v\) contain positive mass \(\mu_v\). Fix \(k\) representatives. Start with an assignment that gives each voter type to an approving representative whenever possible. For any \(\epsilon>0\), reserve an \(\epsilon\)-fraction of every type’s mass for each district, then assign the remainder as before. Every district now has positive mass in every populated cell, so its support is all of \(H\) and is connected. As \(\epsilon\) tends to zero, satisfaction approaches the unconstrained Chamberlin–Courant score for those representatives:
\[ \sum_t \mu_t\,\mathbf{1}[A_t\cap S\ne\varnothing]. \]
So the connectedness requirement often has no effect on the limiting score. Worse, the best score may be only a supremum: every feasible connected allocation loses some satisfaction to the tiny connector shares, but those losses can be made arbitrarily small. The mass version then lacks the maximum that SPR asks for.
This affects both anchors. In the planar singleton-approval mirror of Theorem 1, tiny shares can make both representatives’ districts span the whole connected graph. The same move works on the path in Theorem 2, even with distinct representatives and 2-Approval. Connectivity may still constrain whether the limiting score is *attained*, but it no longer constrains the score’s supremum. That is a singular limit for the paper’s defining feature.
The natural repairs each demand another modeling choice. Requiring a minimum mass at connector cells adds a threshold absent from the paper. Keeping each cell wholly in one district preserves connected partitions, but leaves the network assignment at the cell level indivisible. Preserving the original individual graph exactly may require encoding each person’s network role, making the number of types grow with the population. The coarse-cell model is plausible for shipping, but its mass-splittable connectivity condition lets vanishingly small cohorts determine whether a district is connected.
This is a serious objection to a stable continuous *optimization* mirror, but it does not fully defeat the anchors. A decision question at an exact target—especially whether the unconstrained score is attained—could still retain the connectivity combinatorics and could be worth studying. The proponent’s mass problem is mathematically well-defined as a threshold feasibility problem, and the paper’s scenarios make a coarse network model plausible. I can make the negative case that the natural mass objective degenerates; I cannot honestly claim that no worthwhile continuous question survives that endpoint.
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.