Answer: The decision version is \(\mathrm{NP}\text{-complete}\), and exact optimization is \(\mathrm{NP}\text{-hard}\), even for \(k=2\), complete \(G\), unit populations, \(\epsilon=0\), and constant-true \(Q\).
Theorem 5.2 — class: other
PDF text-layer excerpt — equations and symbol order may be approximateGiven the population centroid Ac, the popu- lation medoid A* can be obtained by solving a constrained min k-cut problem.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a state graph \(G\), voting-block weights, district count \(k\), explicit validity constraints, a rational weight matrix \(\Theta\), and finitely many complete map-preference types with masses \(\mu_t\) summing to one, where type \(t\) selects valid map \(M_t\), compute a valid integral map \(M\) minimizing \(\sum_t \mu_t d_\Theta(A_M,A_{M_t})\), equivalently minimizing \(d_{2,\Theta}(A_M, \sum_t \mu_t A_{M_t})\).
Given an undirected state graph \(G=(V,E)\), let \(m=|V|\geq1\); each voting block has population \(w(v)\in\mathbb Q_{>0}\), and \(1\leq k\leq m\) is part of the input.
A map is an unlabeled partition \(M=\{V_1,\ldots,V_k\}\) into nonempty districts. It is valid when every \(G[V_i]\) is connected, every district population lies in \([(1-\epsilon)W/k,(1+\epsilon)W/k]\), where \(W=\sum_v w(v)\) and \(\epsilon\in\mathbb Q_{\geq0}\), and at most \(C\in\mathbb Z_{\geq0}\) edges of \(G\) cross districts.
Additional validity constraints are supplied as a Boolean circuit \(Q\) on the same-district matrix and must also hold; the constant-true circuit permits no additional constraints.
A society is given by its support: the list of \(\tau\geq1\) types with positive binary-rational masses \(\mu_t\) satisfying \(\sum_t\mu_t=1\). Each type supplies its selected valid map \(M_t\); \(\tau\) is the support size, not the number of possible types. A type's remaining preferences play no role.
Define \(A_M(i,j)=1\) exactly when \(i,j\) share a district, and zero otherwise. The input matrix \(\Theta\) has binary-rational entries \(\theta(i,j)>0\); symmetry is not required.
Define \(d_\Theta(A,B)=\frac12\sum_{i,j\in V}\theta(i,j)|A(i,j)-B(i,j)|\) and \(d_{2,\Theta}(A,B)=\frac12\sum_{i,j\in V}\theta(i,j)(A(i,j)-B(i,j))^2\).
Minimize \(F(M)=\sum_t\mu_t d_\Theta(A_M,A_{M_t})\) over all valid integral maps, equivalently minimizing \(d_{2,\Theta}(A_M,\sum_t\mu_tA_{M_t})\); any minimizing map is acceptable.
Is this exact optimization problem polynomial-time solvable, or is its decision version—whether some valid map has \(F(M)\leq B\), for input \(B\in\mathbb Q_{\geq0}\)—NP-hard? State running times in \(m,\tau,k,L\), where \(L\) is the total binary input length, including all constraints.
Known results: population-medoid optimization with a supplied centroid reduces to constrained minimum \(k\)-cut, potentially with signed weights ([Esmaeili et al.](https://arxiv.org/html/2203.00872v5#S5.SS3)). Ordinary minimum \(k\)-cut is NP-hard for variable \(k\) and polynomial-time solvable for each fixed \(k\) ([Goldschmidt–Hochbaum](https://pubsonline.informs.org/doi/abs/10.1287/moor.19.1.24)). These results do not classify the explicitly supported mass problem above; no such classification was located.
The decision problem is \(\mathrm{NP}\)-complete, and exact optimization is \(\mathrm{NP}\)-hard. This holds even when \(k=2\), \(G\) is complete, all populations are \(1\), \(\epsilon=0\), and \(Q\) is constant true.
The reduction below supplies \(\tau=m-1\) distinct valid maps explicitly. Their masses are dyadic rationals, and \(\Theta\) is symmetric with positive integer entries. Thus hardness does not depend on arbitrary additional constraints or an implicitly represented society.
Define the supported centroid entries and symmetrized distance weights by
\(p_{ij}=\sum_{t=1}^{\tau}\mu_t A_{M_t}(i,j),\qquad q_{ij}=\frac{\theta(i,j)+\theta(j,i)}2.\)
For \(a\in\{0,1\}\), its expected disagreement with the supported entries is \(p_{ij}\) when \(a=0\), and \(1-p_{ij}\) when \(a=1\). Consequently,
\(F(M)=\sum_{i<j}q_{ij}\bigl[p_{ij}+(1-2p_{ij})A_M(i,j)\bigr].\)
Diagonal terms vanish because every map has diagonal entries \(1\).
The stated squared-distance equivalence also follows directly:
\(F(M)=d_{2,\Theta}(A_M,p)+\frac12\sum_{i,j}\theta(i,j)p_{ij}(1-p_{ij}).\)
The second term is independent of \(M\). Computing the centroid is therefore sufficient to evaluate the objective, but finding the best valid integral map remains a separate optimization problem.
We use the known \(\mathrm{NP}\)-completeness of unweighted maximum-cut decision: given a simple graph \(H=(U,D)\) and an integer \(K\), decide whether some cut contains at least \(K\) edges. This is established by [Garey, Johnson, and Stockmeyer](https://doi.org/10.1016/0304-3975%2876%2990059-1).
Write \(n=|U|\) and \(h=|D|\). We may assume \(n\geq2\) and \(0\leq K\leq h\): isolated vertices ensure the first condition, and thresholds outside the second range are trivial.
Choose the smallest power of two \(m=2^r\) satisfying \(m\geq\max\{2n,4\}\). Identify the state vertices with \(V=\{0,1\}^r\), and embed \(U\) injectively into \(V\). The remaining vertices are dummy vertices.
Set
\(G=K_m,\qquad k=2,\qquad w(x)=1,\qquad \epsilon=0,\qquad C=m^2/4,\)
and let \(Q\) be constant true.
The valid maps are exactly the bipartitions with two districts of size \(m/2\). Indeed, exact population balance forces those sizes; both induced districts are connected in the complete graph; and every such bipartition has exactly \(m^2/4\) crossing edges.
Every cut of \(H\) extends to a valid map. If its sides contain \(a\) and \(n-a\) source vertices, add respectively \(m/2-a\) and \(m/2-(n-a)\) dummy vertices. Both numbers are nonnegative because \(n\leq m/2\), and their sum is \(m-n\).
All vector additions and dot products in this construction are over the binary field. For each nonzero \(s\in\{0,1\}^r\), define
\(\chi_s(x)=(-1)^{s\cdot x}\)
and supply the map
\(M_s=\bigl\{\{x:\chi_s(x)=1\},\{x:\chi_s(x)=-1\}\bigr\}.\)
A nonzero linear form takes each binary value on exactly \(m/2\) vertices. Hence every supplied map is valid.
These maps are distinct as unlabeled partitions. Their positive district always contains the zero vector, and distinct linear forms differ on some vertex. Thus \(\tau=m-1\).
Fix one nonzero \(s_*\), and assign masses
\(\mu_{s_*}=\frac{m+2}{m^2},\qquad \mu_s=\frac{m+1}{m^2}\quad(s\ne s_*).\)
They are positive dyadic rationals, and
\(\sum_{s\ne0}\mu_s=\frac{(m+2)+(m-2)(m+1)}{m^2}=1.\)
For distinct \(x,y\), character orthogonality gives
\(\sum_{s\in\{0,1\}^r}\chi_s(x)\chi_s(y)=0.\)
To justify this, \(x+y\ne0\), so there exists \(z\) with \(z\cdot(x+y)=1\). Pairing each summand indexed by \(s\) with the summand indexed by \(s+z\) cancels the sum. Removing the term indexed by zero therefore gives
\(\sum_{s\ne0}\chi_s(x)\chi_s(y)=-1.\)
Define
\(\delta_{xy}=\chi_{s_*}(x)\chi_{s_*}(y),\qquad c_{xy}=m+1-\delta_{xy}\in\{m,m+2\}.\)
The supported sign correlation is
\(\rho_{xy}=\sum_{s\ne0}\mu_s\chi_s(x)\chi_s(y) =\frac{m+1}{m^2}(-1)+\frac{\delta_{xy}}{m^2} =-\frac{c_{xy}}{m^2}.\)
Two vertices share a district exactly when their signs agree. Hence
\(p_{xy}=\frac{1+\rho_{xy}}2 =\frac12-\frac{c_{xy}}{2m^2},\qquad 1-2p_{xy}=\frac{c_{xy}}{m^2}>0.\)
This calculation uses precisely the explicitly listed supported maps.
For each unordered pair, define
\(\alpha_{xy}= \begin{cases} 2,&\{x,y\}\in D,\\ 1,&\{x,y\}\notin D, \end{cases}\)
where source edges are viewed through the embedding into \(V\). Set the symmetric off-diagonal entries to
\(\theta(x,y)=\theta(y,x)=\alpha_{xy}\frac{m(m+2)}{c_{xy}},\)
and set \(\theta(x,x)=1\).
Because \(c_{xy}\in\{m,m+2\}\), every off-diagonal entry belongs to
\(\{m,m+2,2m,2(m+2)\}.\)
In particular, all entries are positive integers. Moreover,
\(\theta(x,y)(1-2p_{xy})=\alpha_{xy}\frac{m+2}{m}.\)
Let
\(\lambda=\frac{m+2}{m},\qquad F_0=\sum_{x<y}\theta(x,y)p_{xy}.\)
The objective formula from Section 1 becomes
\(F(M)=F_0+\lambda\sum_{x<y}\alpha_{xy}A_M(x,y).\)
For a valid map \(M\), let \(c_H(M)\) denote the number of source edges whose endpoints lie in different districts.
Every balanced bipartition has exactly
\(b=2\binom{m/2}{2}=\frac{m(m-2)}4\)
same-district unordered pairs. Since \(\alpha_{xy}\) adds one extra unit precisely on source edges,
\(\sum_{x<y}\alpha_{xy}A_M(x,y)=b+h-c_H(M).\)
Thus the exact identity is
\(F(M)=F_0+\lambda\bigl(b+h-c_H(M)\bigr).\)
Supply the threshold
\(B=F_0+\lambda(b+h-K).\)
It is nonnegative because \(F_0\geq0\), \(b\geq0\), and \(K\leq h\). Since \(\lambda>0\),
\(F(M)\leq B\quad\Longleftrightarrow\quad c_H(M)\geq K.\)
Every valid map restricts to a cut of \(H\), and every cut of \(H\) extends to a valid map. Therefore the source and target decision instances have the same answer. The same identity shows that any optimizing map restricts to a maximum cut of \(H\).
Here \(m=O(n)\) and \(\tau=m-1\). Every numerical datum has \(O(\log m)\) bits, including \(B\): the entries \(p_{xy}\) have common denominator \(2m^2\), so \(F_0\) and \(B\) can be computed with polynomially bounded numerators.
The entire output has length \(L=O(m^2\log m)\) under standard explicit encodings. A direct construction takes \(O(m^2(\log m)^2)\) bit operations. This is a polynomial-time reduction.
A certificate assigns each vertex a district label in \(\{1,\ldots,k\}\), using \(O(m\log k)\) bits. A verifier checks nonempty districts, connectivity, population bounds, crossing-edge count, circuit acceptance, and the objective threshold.
All these checks use exact rational arithmetic. To make the bit complexity explicit, use products of input denominators as common denominators. Their binary lengths are \(O(L)\); all intermediate integers in these checks also have \(O(L)\) bits. Schoolbook integer arithmetic therefore gives polynomial bit complexity.
A direct certificate verifier runs in
\(O\bigl((\tau m^2+m^2+L)L^2\bigr)\)
bit operations. Thus the decision problem belongs to \(\mathrm{NP}\), completing the \(\mathrm{NP}\)-completeness proof.
For general exact optimization, compute the centroid and objective coefficients once, then enumerate all \(k^m\) district-label assignments, discarding invalid ones. This yields the explicit upper bound
\(O\bigl((\tau m^2+k^m(m^2+L))L^2\bigr)\)
bit operations. Duplicate labeled representations of an unlabeled partition do not affect correctness.
The hardness result rules out a polynomial-time algorithm in \(m,\tau,k,L\), unless \(\mathrm{P}=\mathrm{NP}\). It already holds with \(k=2\), so fixing the number of districts does not suffice.
For \(k=1\) or \(k=m\), there is only one partition. The supplied-valid-map premise guarantees its validity.
There is also a useful support-based tractable case: if some type \(s\) has \(\mu_s\geq1/2\), its selected map \(M_s\) is optimal. The triangle inequality for the weighted entrywise distance gives
\(F(M)\geq F(M_s)+(2\mu_s-1)d_\Theta(A_M,A_{M_s})\geq F(M_s).\)
Consequently, \(\tau\leq2\) is polynomial-time solvable by selecting a type of maximum mass. Its objective value can be computed in \(O((\tau m^2+L)L^2)\) bit operations.
Finally, the fixed-\(k\) polynomial algorithm for ordinary minimum \(k\)-cut does not classify this problem. In the reduction, every coefficient of \(A_M(x,y)\) is positive; rewriting \(A_M(x,y)\) as one minus the crossing indicator produces negative cut coefficients. The resulting objective maximizes a cut quantity, as the proved identity demonstrates.
⟨structured verdict parsed — rendered above⟩
The prover resolves the assigned problem correctly. The reduction proves NP-hardness under all the advertised restrictions, and the verification argument establishes membership in \(\mathrm{NP}\). I found no major or minor mathematical issues.
1. Objective formulas
The symmetrization is correct even when \(\Theta\) is asymmetric. Since same-district matrices are symmetric, combining the two ordered off-diagonal terms gives weight \(q_{ij}=(\theta(i,j)+\theta(j,i))/2\). Diagonal disagreements vanish.
For binary \(a\), the expected disagreement is \(p_{ij}+(1-2p_{ij})a\), so the displayed formula for \(F(M)\) is correct.
The squared-distance identity is also correct: the difference between expected binary disagreement and squared distance to the centroid is \(p_{ij}(1-p_{ij})\). Its weighted sum is independent of the candidate map. Thus the claimed equivalence concerns minimizers; it does not mistakenly equate the two objective values.
2. Source problem and reduction domain
The cited theorem supplies the required NP-completeness of unweighted maximum-cut decision. The publisher’s abstract explicitly identifies Simple Max Cut as maximum cut with every edge weight equal to one. [Garey–Johnson–Stockmeyer](https://www.sciencedirect.com/science/article/pii/0304397576900591)
The reduction uses exactly this setting: a simple graph and an integer cut threshold. Restricting to \(n\geq2\) and \(0\leq K\leq h\) causes no hardness gap. Isolated vertices preserve cut values, and thresholds outside that range have immediate answers.
Choosing the smallest power of two above \(\max\{2n,4\}\) gives an even \(m=O(n)\). All subsequent parameters satisfy the task’s domains.
3. Characterization of valid maps
With unit populations, \(k=2\), and \(\epsilon=0\), each district must contain exactly \(m/2\) vertices. These districts are nonempty and connected in \(K_m\). Every such partition has exactly \(m^2/4\) crossing edges, so the chosen crossing bound accepts every balanced bipartition. The constant-true circuit introduces no restriction.
The statement that these are exactly the valid maps is therefore correct.
The extension argument also checks out. For source-side sizes \(a\) and \(n-a\), both prescribed dummy counts are nonnegative because \(n\leq m/2\). Their sum is exactly the available number \(m-n\) of dummy vertices. Conversely, restricting a valid map to the source vertices gives a cut of \(H\). Empty source sides cause no problem.
4. Explicit support and masses
Every nonzero binary linear form has two fibers of size \(m/2\), so every supplied map is valid.
Distinctness holds for unlabeled partitions: the district containing the zero vector identifies the positive fiber uniquely. Distinct linear forms differ somewhere, so their positive fibers differ. Hence the support really has \(\tau=m-1\) distinct maps.
The masses are positive and dyadic because \(m^2\) is a power of two. Their normalization is exact: the numerator \((m+2)+(m-2)(m+1)\) equals \(m^2\).
There is no implicit or exponentially encoded society in this construction.
5. Centroid calculation
The orthogonality argument is valid. For distinct \(x,y\), the vector \(x+y\) is nonzero. Translation by a vector \(z\) satisfying \(z\cdot(x+y)=1\) pairs summands with their negatives. Removing the zero-character term leaves the stated sum \(-1\).
The distinguished mass exceeds each other mass by exactly \(1/m^2\). Therefore the displayed correlation is correctly calculated as \(\rho_{xy}=-(m+1-\delta_{xy})/m^2\).
Consequently, both centroid formulas are correct:
The calculation covers every off-diagonal pair. Diagonal entries are already handled separately.
6. Distance weights and objective identity
Since \(c_{xy}\) is either \(m\) or \(m+2\), the proposed distance weights are positive integers in the stated four-element set. Symmetry and positive diagonal entries satisfy all requirements on \(\Theta\).
Multiplication gives exactly \(\theta(x,y)(1-2p_{xy})=\alpha_{xy}(m+2)/m\). There is no missing factor of two: the objective has already been expressed over unordered pairs.
Every balanced bipartition has \(b=m(m-2)/4\) same-district unordered pairs. The extra unit in \(\alpha_{xy}\) counts precisely those source edges remaining within districts, namely \(h-c_H(M)\). Thus the central identity
\(F(M)=F_0+\lambda(b+h-c_H(M))\)
is correct.
As supplementary arithmetic checks, direct exact-rational evaluation confirmed this identity for all three unlabeled balanced maps when \(m=4\) with a single source edge, and all 35 when \(m=8\) with a source triangle. These checks support, but do not replace, the written algebra.
7. Threshold and hardness conclusion
The threshold is an admissible nonnegative rational: \(F_0\geq0\), \(b\geq0\), and \(h-K\geq0\).
Because \(\lambda>0\), the equivalence \(F(M)\leq B\) if and only if \(c_H(M)\geq K\) follows with the correct inequality direction. Together with the restriction and extension properties, this proves a polynomial many-one reduction.
The same identity supports the optimization claim: every minimizing valid map restricts to a maximum cut. All advertised restrictions hold simultaneously.
8. Encoding and running times
The reduction’s encoding claims are consistent under standard explicit encodings. There are \(O(m^2)\) support labels and matrix entries, each requiring at most \(O(\log m)\) bits. The common denominator \(2m^2\) for centroid entries keeps the threshold’s numerator and denominator polynomially bounded in magnitude, hence of \(O(\log m)\) binary length.
The stated construction time \(O(m^2(\log m)^2)\) is sufficient for the character calculations, output construction, and exact threshold arithmetic.
For membership in \(\mathrm{NP}\), district labels describe a polynomial-size certificate. The listed checks cover every validity requirement and the objective threshold. Products of input denominators have \(O(L)\) binary length; the relevant rational calculations retain \(O(L)\)-bit intermediate integers when performed with common denominators.
The claimed verifier bound \(O((\tau m^2+m^2+L)L^2)\) is a valid conservative polynomial bound.
The exhaustive optimization bound \(O((\tau m^2+k^m(m^2+L))L^2)\) is also consistent. Enumeration includes every unlabeled partition through its labeled representations, and duplicates do not affect minimization. Feasibility is guaranteed by the supplied-valid-map premise.
9. Additional tractable cases
The unique-partition statements for \(k=1\) and \(k=m\) correctly use that premise to guarantee validity.
The majority-mass inequality follows from the triangle inequality with the stated coefficient \(2\mu_s-1\). Thus a supplied map of mass at least one half is optimal, including equality. For \(\tau\leq2\), such a type necessarily exists.
Finally, the explanation concerning ordinary minimum \(k\)-cut is correct: replacing same-district indicators by one minus crossing indicators makes the reduction’s cut coefficients negative. The cited fixed-\(k\) result for ordinary minimum \(k\)-cut therefore does not contradict this hardness result.
No repair or additional clarification is required.
⟨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.