Answer: \(\mathrm{NP}\text{-complete}\), and hence \(\mathrm{NP}\text{-hard}\), even for uniform masses \(\mu_v=1/|V|\)
Theorem 3.3 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateFor planar graphs, finding a partition with one winning district is NP-hard.
statement extracted from the paper’s text layer; consult the paper for the exact wording
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\}\)?
Definitions. An instance consists of a planar graph \(G=(V,E)\), candidates \(C\), a target \(b\in C\), an approval map \(a:V\to C\), an integer \(k\), and rational masses \(\mu_v>0\) with \(\sum_{v\in V}\mu_v=1\). A district \(D\subseteq V\) is connected when \(G[D]\) is connected; \(b\) wins \(D\) when \(\sum_{v\in D:a(v)=b}\mu_v>\sum_{v\in D:a(v)=c}\mu_v\) for every \(c\in C\setminus\{b\}\).
Target. Is deciding whether \(V\) admits a partition into \(k\) nonempty connected districts with at least one district won by \(b\) solvable in polynomial time, or NP-hard?
Nearest known results. For unweighted planar graphs with an unrestricted number of candidates, deciding whether a partition with one winning district exists is NP-hard. The rational-mass formulation above permits arbitrary positive rational vertex masses summing to \(1\).
Under the stated known NP-hardness result, the rational-mass problem is \( \mathrm{NP} \)-complete. In particular, it is \( \mathrm{NP} \)-hard even when every vertex has the same mass.
Consider the known unweighted problem from the prompt. An instance consists of a planar graph \(G=(V,E)\), candidates \(C\), a target candidate \(b\), an approval map \(a:V\to C\), and an integer \(k\). Candidate \(b\) wins a district \(D\) precisely when
\[ \left|\{v\in D:a(v)=b\}\right| > \left|\{v\in D:a(v)=c\}\right| \]
for every \(c\in C\setminus\{b\}\). By hypothesis, deciding whether there is a partition into \(k\) nonempty connected districts having at least one such district is NP-hard, even when \(G\) is planar.
Let \(n=|V|\). The existence of positive masses summing to \(1\) implies that relevant instances have \(n\geq 1\). Construct an instance of the rational-mass problem by retaining \(G,C,b,a,k\) and assigning
\[ \mu_v=\frac{1}{n} \]
to every \(v\in V\). These masses are positive and satisfy
\[ \sum_{v\in V}\mu_v=n\cdot\frac1n=1. \]
For any district \(D\subseteq V\) and candidate \(c\in C\),
\[ \sum_{v\in D:a(v)=c}\mu_v = \frac{\left|\{v\in D:a(v)=c\}\right|}{n}. \]
Because multiplication by the positive number \(n\) preserves strict inequalities, for every \(c\neq b\),
\[ \sum_{v\in D:a(v)=b}\mu_v > \sum_{v\in D:a(v)=c}\mu_v \]
holds if and only if
\[ \left|\{v\in D:a(v)=b\}\right| > \left|\{v\in D:a(v)=c\}\right|. \]
Thus \(b\) wins exactly the same subsets \(D\) in the unweighted instance and in the rational-mass instance. Connectivity, nonemptiness, the graph, and the required number \(k\) of districts are unchanged. Consequently, the original instance is a yes-instance if and only if the constructed rational-mass instance is a yes-instance.
Each mass \(1/n\) has binary encoding length \(O(\log n)\), so the construction has polynomial size and is computable in polynomial time. It also preserves planarity. This proves NP-hardness.
A certificate assigns each vertex one of the \(k\) district labels.
It can be verified in polynomial time that:
Sums and comparisons of binary-encoded rational numbers can be performed using integer arithmetic whose bit complexity is polynomial in the input length. Hence the problem belongs to \( \mathrm{NP} \).
Combining membership in \( \mathrm{NP} \) with the reduction above proves \( \mathrm{NP} \)-completeness. Therefore it is not polynomial-time solvable unless \( \mathrm{P}=\mathrm{NP} \).
⟨structured verdict parsed — rendered above⟩
The prover correctly reduces the stated unweighted planar problem to the rational-mass problem by assigning every vertex mass \(1/n\). The reduction preserves exactly which districts are won by \(b\), as well as connectivity, nonemptiness, the number of districts, and planarity.
The membership-in-\(\mathrm{NP}\) argument is also correct. Therefore, accepting the nearest known NP-hardness result supplied in the task, the prover establishes \(\mathrm{NP}\)-completeness and hence fully answers the requested polynomial-time-versus-\(\mathrm{NP}\)-hard classification.
No substantive or expositional issue affecting verifiability was found.
⟨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.