Answer: polynomial-time solvable
Theorem 1 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateSPR is NP-hard, even when each voter can approve only one alternative, the number of districts is two, there are only three alternatives, and the graph is planar.
statement extracted from the paper’s text layer; consult the paper for the exact wording
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\)?
Given a finite simple undirected planar cell graph \(H=(P,F)\), alternatives \(C=\{a_1,a_2,a_3\}\), and a binary-rational threshold \(q\), a type \((v,a)\) is located at cell \(v\) and approves only \(a\).
A society is given by its support: the list of the \(\tau\) types with positive mass, each with its mass as a binary rational. Here \(\tau\) is the support size, not the number of possible types; unlisted types have mass zero, and \(\sum_{v\in P,a\in C}\mu_{v,a}=1\).
Choose exactly two representatives \(r_1,r_2\in C\), allowing repetitions, and real allocations \(x_{v,a,j}\geq 0\) satisfying \(x_{v,a,1}+x_{v,a,2}=\mu_{v,a}\) for every type.
For each \(j\in\{1,2\}\), require \(S_j=\{v\in P:\sum_{a\in C}x_{v,a,j}>0\}\) to be nonempty and \(H[S_j]\) to be connected. The supports may overlap; cells with zero allocated mass cannot provide connectivity.
Feasibility additionally requires \(\sum_{j=1}^{2}\sum_{v\in P}x_{v,r_j,j}\geq q\). There are no district-size constraints.
State running times in \(m=|C|=3\), \(\tau\), \(|P|\), \(|F|\), and the total input bit length \(L\).
Is this continuous feasibility problem solvable in polynomial time, or is it NP-hard?
The discrete version, with one indivisible singleton-approval voter per vertex, is NP-hard on planar graphs with three alternatives and exactly two districts, including when representatives may repeat. [Talmon, 2017](https://www.ifaamas.org/AAMAS/aamas2017/proceedings/pdfs/p633.pdf)
No result settling this exact continuous problem was located in the literature search.
The continuous feasibility problem is polynomial-time solvable. In fact, the algorithm works for arbitrary finite simple undirected graphs; planarity is unnecessary.
With \(m=3\), its bit running time is bounded by \(O((|P|+|F|+\tau)L^2)\). Keeping the dependence on the number of alternatives explicit, the bound is \(O(m^2(|P|+|F|+\tau)L^2)\).
Define the total mass at cell \(v\) by \(w_v=\sum_{a\in C}\mu_{v,a}\), and let
\(V^+=\{v\in P:w_v>0\},\qquad G=H[V^+].\)
For every allocation, conservation of mass implies \(S_1\cup S_2=V^+\). Moreover, each connected support lies entirely within one connected component of \(G\). Consequently, if \(G\) has more than two connected components, the instance is infeasible, independently of the threshold.
The normalization \(\sum_{v,a}\mu_{v,a}=1\) ensures that \(V^+\) is nonempty.
If \(G\) has exactly two connected components \(D_1,D_2\), each district must occupy one entire component: neither support can meet both components, and together the supports must cover all occupied cells. Thus the maximum satisfaction is exactly
\(\displaystyle \max_{a\in C}\sum_{v\in D_1}\mu_{v,a}+\max_{a\in C}\sum_{v\in D_2}\mu_{v,a}.\)
This value is attained by allocating all mass in each component to its district and choosing a maximizing representative there. Representatives may coincide. Comparing this value with \(q\) settles this case.
Henceforth, assume that \(G\) is connected.
For each alternative \(a\), define its total approving mass by
\(\displaystyle W_a=\sum_{v\in V^+}\mu_{v,a}.\)
If both representatives equal \(a\), satisfaction is always exactly \(W_a\), because every type approving \(a\) is satisfied regardless of its allocation. Splitting every positive type equally between the two districts gives \(S_1=S_2=V^+\), so both supports are nonempty and connected.
Therefore, if \(q\leq\max_{a\in C}W_a\), the instance is feasible.
For distinct representatives \(r,s\), assign \(r\) to district \(1\) and \(s\) to district \(2\). Set \(U_{r,s}=W_r+W_s\). Conservation gives the identity
\(\displaystyle \operatorname{sat}(x)=U_{r,s}-\sum_{v\in V^+}\bigl(x_{v,r,2}+x_{v,s,1}\bigr).\)
In particular, satisfaction cannot exceed \(U_{r,s}\). Equality holds precisely when
\(x_{v,r,2}=x_{v,s,1}=0\quad\text{for every }v\in V^+.\)
This follows because every summand in the loss is nonnegative.
Lemma. For distinct representatives \(r,s\), if \(q<U_{r,s}\), there is a feasible allocation.
Proof. Write \(U=U_{r,s}\), and choose the positive rational
\(\displaystyle \varepsilon=\min\left\{\frac14,\frac{U-q}{2}\right\}.\)
Allocate a fraction \(1-\varepsilon\) of every type approving \(r\) to district \(1\), and its remaining fraction to district \(2\). Allocate types approving \(s\) symmetrically. Split every other positive type equally between the districts.
Both districts receive positive mass at every occupied cell. Thus \(S_1=S_2=V^+\), and connectivity follows from the assumed connectivity of \(G\).
The satisfaction is \((1-\varepsilon)U\). Since \(U\leq1\),
\(\displaystyle (1-\varepsilon)U\geq U-\varepsilon\geq U-\frac{U-q}{2}=\frac{U+q}{2}>q.\)
All allocation and threshold requirements are therefore satisfied. \(\square\)
The equality case requires a separate argument: arbitrarily small positive losses cannot meet an exact threshold.
Fix distinct representatives \(r,s\) with \(W_r>0\) and \(W_s>0\). Let \(t\) be the third alternative, and define
\(T_1=\{v:\mu_{v,r}>0\},\qquad T_2=\{v:\mu_{v,s}>0\},\)
\(A_1=\{v:\mu_{v,r}+\mu_{v,t}>0\},\qquad A_2=\{v:\mu_{v,s}+\mu_{v,t}>0\}.\)
All these sets are subsets of \(V^+\).
Choose any \(u_1\in T_1\), and let \(K_1\) be its connected component in \(G[A_1]\). Likewise, choose any \(u_2\in T_2\), and let \(K_2\) be its connected component in \(G[A_2]\).
Lemma. An allocation attaining satisfaction \(U_{r,s}\) exists if and only if
\(T_1\subseteq K_1,\qquad T_2\subseteq K_2,\qquad K_1\cup K_2=V^+.\)
Necessity. Equality in the score bound forces all mass approving \(r\) into district \(1\), and all mass approving \(s\) into district \(2\). Hence \(T_1\subseteq S_1\) and \(T_2\subseteq S_2\).
District \(1\) receives no mass approving \(s\). Every cell in its support must therefore have positive mass approving \(r\) or \(t\), so \(S_1\subseteq A_1\). Similarly, \(S_2\subseteq A_2\).
Because \(S_1\) is connected and contains \(u_1\), it lies within \(K_1\). Thus \(T_1\subseteq K_1\); the corresponding conclusion holds for district \(2\). Finally,
\(V^+=S_1\cup S_2\subseteq K_1\cup K_2\subseteq V^+,\)
which proves the covering condition.
Sufficiency. Suppose the three conditions hold. Allocate all mass approving \(r\) to district \(1\), and all mass approving \(s\) to district \(2\). Allocate mass approving \(t\) as follows:
These rules cover every occupied cell and conserve every type’s mass.
We verify that the resulting supports are exactly \(K_1,K_2\). At a cell in \(K_1\setminus K_2\), the inclusion \(T_2\subseteq K_2\) implies \(\mu_{v,s}=0\). All its positive mass therefore goes to district \(1\). The symmetric statement holds in \(K_2\setminus K_1\).
At a cell in the intersection, positive mass approving \(t\) supplies both districts. If that mass is zero, membership in both \(A_1\) and \(A_2\) implies \(\mu_{v,r}>0\) and \(\mu_{v,s}>0\); these masses again supply both districts.
Consequently, the supports are exactly the nonempty connected sets \(K_1,K_2\). Every type approving either selected representative is satisfied, giving satisfaction \(U_{r,s}\). \(\square\)
First compute the connected components of the occupied graph \(G\).
The equality test’s hypotheses hold whenever it is reached. Indeed, Step 3 has already established \(q>\max_a W_a\). If \(q=W_r+W_s\), neither \(W_r\) nor \(W_s\) can be zero.
Every acceptance has an explicit feasible allocation from the preceding proofs. Conversely, any feasible allocation uses either repeated representatives, covered by Step 3, or a distinct pair. For that pair, the score bound excludes \(q>U_{r,s}\); strict inequality is covered by Section 3, and equality necessarily passes the criterion in Section 4. Thus the algorithm is complete.
The support list constructs the masses and occupied cells without introducing any unlisted positive types. There are at most \(\tau\) occupied cells.
Using adjacency lists, the initial graph computation takes \(O(|P|+|F|+\tau)\) operations for \(m=3\). Each equality test uses two graph searches and a scan of the occupied cells, taking \(O(|P|+|F|)\) operations. There are at most \(O(m^2)\) representative pairs.
For exact arithmetic, take the product of the denominators appearing in the masses and threshold as a common denominator. Its binary length is \(O(L)\), since the sum of the input denominator lengths is at most \(L\). Scaling the inputs and performing all subsequent comparisons therefore uses integers of \(O(L)\) bits. Ordinary integer arithmetic yields the conservative bit bound
\(\displaystyle O\!\left(m^2(|P|+|F|+\tau)L^2\right).\)
For \(m=3\), this is \(O((|P|+|F|+\tau)L^2)\). The constructions also produce rational allocations of polynomial encoding length.
Consider a three-cell path whose endpoint cells each carry mass \(1/4\) approving \(a_1\), while its middle cell carries mass \(1/2\) approving \(a_2\). Alternative \(a_3\) has no mass.
Every threshold \(q<1\) is feasible by Section 3. Threshold \(q=1\) is infeasible: full satisfaction requires representatives \(a_1,a_2\), with both endpoints entirely in the first district and the middle cell entirely in the second. The first support is disconnected. Thus the supremum satisfaction need not be attained.
The discrete hardness result concerns a partition into disjoint connected districts. [Talmon, Theorem 1](https://www.ifaamas.org/AAMAS/aamas2017/proceedings/pdfs/p633.pdf) Continuous splitting and overlapping supports change that requirement, and the algorithm above settles the stated continuous problem.
⟨structured verdict parsed — rendered above⟩
The prover resolves the stated continuous feasibility problem. The allocation arguments, equality criterion, decision algorithm, and polynomial bit-complexity bound are correct. I found no major or minor mathematical issues.
Nonnegativity and conservation imply that an unlisted or zero-mass type receives zero allocation in both districts. At every positive-mass cell, at least one district receives positive mass. Therefore, \(S_1\cup S_2=V^+\), as claimed.
Since both supports lie in \(V^+\), their connectivity must be witnessed within \(G=H[V^+]\). Each support consequently lies within one connected component of \(G\). Two supports cannot cover more than two components.
Normalization guarantees \(V^+\ne\varnothing\), so the algorithm correctly omits a zero-component case.
If \(G\) has exactly two components, each must be covered by a support. Neither support can cross components, so the two districts occupy different components and each covers its entire component.
Conservation then assigns every type in a component entirely to its corresponding district. Maximizing the representative separately in each component gives exactly the displayed satisfaction value. Both districts are nonempty and connected, and repeated representatives are permitted.
This case is fully resolved.
For repeated representative \(a\), all mass approving \(a\) is satisfied and no other mass is satisfied. Thus satisfaction is exactly \(W_a\), independently of the allocation.
In connected \(G\), dividing every positive type equally makes both supports exactly \(V^+\). This also works when \(V^+\) consists of a single cell.
For distinct representatives \(r,s\), conservation gives the stated identity:
\[
\operatorname{sat}(x)=W_r+W_s-\sum_{v\in V^+}(x_{v,r,2}+x_{v,s,1}).
\]
Every loss term is nonnegative. Hence the upper bound and its equality characterization are both correct.
When \(q<U\), the chosen rational \(\varepsilon\) satisfies \(0<\varepsilon\le 1/4\). Thus every positive type contributes positive mass to both districts under the prescribed allocation. Both supports are exactly \(V^+\).
The satisfaction calculation \((1-\varepsilon)U\) is correct. Normalization gives \(0\le U\le1\), and both inequalities in
\[
(1-\varepsilon)U\ge U-\varepsilon\ge\frac{U+q}{2}>q
\]
have the correct direction.
The lemma also covers \(U=0\): its hypothesis then requires \(q<0\), and zero satisfaction exceeds \(q\). No positivity assumption on \(q\) is missing.
Attaining \(U_{r,s}\) forces every \(r\)-approving type into district \(1\) and every \(s\)-approving type into district \(2\). Therefore \(T_1\subseteq S_1\) and \(T_2\subseteq S_2\).
District \(1\) can receive mass only from alternatives \(r,t\), giving \(S_1\subseteq A_1\); the corresponding inclusion holds for district \(2\).
A connected support containing \(u_j\) must lie in the component \(K_j\) of the relevant induced graph. The terminal-containment conditions follow. Coverage follows from \(S_1\cup S_2=V^+\).
These steps establish all three necessary conditions without an unstated connectivity assumption.
The stated allocation conserves every type’s mass.
On \(K_1\setminus K_2\), terminal containment excludes positive \(s\)-mass. Membership in \(K_1\subseteq A_1\) guarantees positive mass available to district \(1\). The symmetric statement holds on \(K_2\setminus K_1\).
On \(K_1\cap K_2\), positive \(t\)-mass supplies both districts. If \(t\)-mass is zero, membership in both allowed sets guarantees positive \(r\)-mass and positive \(s\)-mass, again supplying both districts.
Terminal containment also ensures that the prescribed \(r\)- and \(s\)-allocations create no support outside their respective \(K_j\). Consequently, the supports are exactly \(K_1,K_2\). Each is connected and nonempty, and satisfaction is exactly \(U_{r,s}\).
The criterion is therefore sufficient as well as necessary.
The algorithm exhausts the possibilities for the number of occupied components and for repeated or distinct representatives.
Whenever the equality test is reached, \(q>\max_a W_a\). Together with \(q=W_r+W_s\), this implies \(W_r>0\) and \(W_s>0\), so both chosen terminals exist.
Unordered pairs suffice: exchanging district labels exchanges the two representatives without changing feasibility.
Thresholds outside the interval from zero to one require no additional branch. The existing comparisons handle them correctly. Every acceptance is justified by a feasible allocation, and every rejection excludes all representative choices.
The support representation is respected throughout: the number of occupied cells is at most \(\tau\), and unlisted types remain zero. The graph searches and scans have the claimed operation counts.
The product of input denominators has \(O(L)\) bits. Scaling rational inputs to that denominator preserves \(O(L)\)-bit integer sizes; normalized mass totals do not introduce larger integers. Computing the product, scaling inputs, and making exact comparisons fit within the conservative bound
\[
O\!\left(m^2(|P|+|F|+\tau)L^2\right).
\]
For the required \(m=3\), this gives the stated bound. The rational allocation constructions also have polynomial encoding length.
The displayed dependence on \(m\) is assessed for the specified three-alternative problem. Section 4 explicitly uses the third alternative; the write-up does not establish a variable-\(m\) generalization.
The three-cell example is correct. Satisfaction one requires the two positive-mass alternatives as representatives and forces the two endpoints into the same support while excluding the middle cell from that support. Connectivity therefore fails. Strictly smaller thresholds are feasible by the proved strict-threshold lemma.
The cited discrete result concerns connected partitions and includes planar graphs, singleton approvals, three alternatives, two districts, and repeated representatives. This matches [Talmon’s definition and Theorem 1](https://www.ifaamas.org/AAMAS/aamas2017/proceedings/pdfs/p633.pdf). The continuous proof does not depend on that theorem.
No additional clarification or mathematical repair 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.