Answer: \(\mathrm{NP}\text{-hard}\); under the standard finite or real-line encoding of \(Y\), it is \(\mathrm{NP}\text{-complete}\).
Theorem 12 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateGiven an instance ⟨F,Y, N, (pi)i ∈N ,k⟩of the mul- tiwinner facility location problem with |N | = n, it is NP-complete to decide whether there exists a size-k committee that provides JR. The hardness result holds even if there is a value r such that each agent’s approval radius for each facility is either r or −∞.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finite facilities \(F\), rational locations \(Y\), committee size \(k\), and a finite set of complete profile types \(T\) with rational masses \(\mu_t\) summing to \(1\), where type \(t=(x_t,(r_{tf})_{f\in F})\) approves the facility-location pairs \(A_t\subseteq F\times Y\) induced by the paper's radii, decide whether there exists a compatible size-\(k\) committee \(W\) such that for every \(c\in(F\times Y)\setminus W\), \(\sum_{t:\,c\in A_t,\;A_t\cap W=\varnothing}\mu_t<\frac{1}{k}\).
Let \(C=F\times Y\). Each type \(t\in T\) has rational location \(x_t\), radii \(r_{tf}\in\mathbb{Q}_{\ge0}\cup\{-\infty\}\), and mass \(\mu_t\in\mathbb{Q}_{\ge0}\), with \(\sum_{t\in T}\mu_t=1\); it approves \((f,y)\) iff \(r_{tf}\ne-\infty\) and \(|x_t-y|\le r_{tf}\). Candidates are compatible iff they use distinct facilities and distinct locations. A committee is a pairwise-compatible \(W\subseteq C\) of size \(k\).
Target. Is it NP-hard, or solvable in polynomial time, to decide whether there is such a committee \(W\) for which every \(c\in C\setminus W\) satisfies
\(\sum_{t:\,c\in A_t,\ A_t\cap W=\varnothing}\mu_t<\frac1k\)?
Known results. For explicitly listed finite agents in the no-co-location model, deciding whether a size-\(k\) committee satisfying justified representation exists is NP-complete, even when every approval radius is either one common value or \(-\infty\).
A discretization result for continuous facility locations with finitely many agents does not address this distribution-over-types formulation.
The problem is \(\mathrm{NP}\)-hard. In fact, under the standard encoding where \(Y\) is either explicitly finite or is the real line with rational interval endpoints, it is \(\mathrm{NP}\)-complete.
Consider an instance of the known \(\mathrm{NP}\)-complete problem with agents \(N=\{1,\ldots,n\}\). Agent \(i\) has location \(x_i\), radii \(r_{if}\), and approval set \(A_i\). The candidate set, compatibility relation, and committee size \(k\) are as in the target problem.
For a committee \(W\) and candidate \(c\), define
\[ U_c(W)=\{i\in N:c\in A_i\text{ and }A_i\cap W=\varnothing\}. \]
The committee violates justified representation exactly when some candidate \(c\) has
\[ |U_c(W)|\geq \frac{n}{k}. \]
Indeed, \(U_c(W)\) itself is then an unrepresented group of quota size whose members all approve \(c\). Conversely, every unrepresented quota-size group with a commonly approved candidate \(c\) is contained in \(U_c(W)\).
If \(c\in W\), then \(U_c(W)=\varnothing\), because every agent approving \(c\) is represented by \(c\). Thus it is equivalent to check only \(c\in C\setminus W\).
For every finite agent \(i\), introduce one type \(t_i\) with
\[ x_{t_i}=x_i,\qquad r_{t_i f}=r_{if},\qquad \mu_{t_i}=\frac1n. \]
The masses are nonnegative rational numbers satisfying
\[ \sum_{i=1}^n\mu_{t_i}=1. \]
The candidate set and compatibility relation are unchanged. Moreover, \(A_{t_i}=A_i\).
If the word “type” requires identical records to be aggregated, merge agents having identical locations and radius vectors. A class containing \(q\) agents receives mass \(q/n\); the argument below is unchanged.
For every committee \(W\) and candidate \(c\),
\[ \sum_{\substack{t:\ c\in A_t\\A_t\cap W=\varnothing}}\mu_t = \frac{|U_c(W)|}{n}. \]
Consequently,
\[ \sum_{\substack{t:\ c\in A_t\\A_t\cap W=\varnothing}}\mu_t < \frac1k \quad\Longleftrightarrow\quad \frac{|U_c(W)|}{n}<\frac1k \quad\Longleftrightarrow\quad |U_c(W)|<\frac nk. \]
Thus a compatible committee satisfies the target mass inequalities if and only if the same committee satisfies justified representation in the original finite-agent instance.
The transformation is polynomial-time: it creates at most \(n\) types, and the rational number \(1/n\) has encoding length \(O(\log n)\). It also preserves the restriction that every radius is either one common rational value or \(-\infty\). Hence the known restricted \(\mathrm{NP}\)-hardness transfers directly.
If \(Y\) is explicitly finite, a proposed committee can be checked by enumerating all candidates and summing the relevant rational masses. This takes polynomial time using exact rational arithmetic.
The same conclusion holds for the usual continuous model \(Y=\mathbb R\). For each finite radius define the closed interval
\[ I_{tf}=[x_t-r_{tf},x_t+r_{tf}]. \]
All interval endpoints are rational. These endpoints partition \(\mathbb R\) into singleton endpoint cells and open interval cells. Within each cell, the set of types approving \((f,y)\) is constant for every facility \(f\).
Any feasible committee can therefore be replaced by one having polynomially encoded rational locations without changing any approval relation:
\[ a+\frac{j}{q+1}(b-a),\qquad j=1,\ldots,q; \]
For a proposed rational committee \(W\), first determine the unrepresented types. For every facility \(f\), the remaining verification is the maximum weighted depth of the intervals \(I_{tf}\) belonging to those types. This depth is constant on every endpoint or open cell and can be computed by a polynomial-time endpoint sweep. Hence the continuous real-line version also belongs to \(\mathrm{NP}\).
The rational distribution-over-types formulation does not remove the known hardness: equal masses \(1/n\) reproduce an explicitly listed electorate exactly. The cited discretization result is not needed for the hardness reduction.
Therefore the target problem is \(\mathrm{NP}\)-hard, even with a single common finite radius together with \(-\infty\); under the standard finite or continuous real-line encoding, it is \(\mathrm{NP}\)-complete.
⟨structured verdict parsed — rendered above⟩
The reduction correctly identifies finite agents with equal-mass types and preserves the relevant justified-representation inequalities exactly. This establishes the claimed hardness, subject to one encoding hypothesis that should be made explicit. The polynomial-time verification arguments for explicitly finite \(Y\) and for \(Y=\mathbb R\) are sound in substance.
For a fixed candidate \(c\), \(U_c(W)\) is precisely the set of unrepresented agents approving \(c\). Therefore an unrepresented group of size at least \(n/k\) with common approved candidate \(c\) exists if and only if \(|U_c(W)|\ge n/k\). This remains correct when \(n/k\) is not an integer.
If \(c\in W\), every agent approving \(c\) is represented, so \(U_c(W)=\varnothing\). Thus checking only \(C\setminus W\) is equivalent.
Assigning one type of mass \(1/n\) to each agent preserves approval sets and yields total mass \(1\). Aggregating identical records into mass \(q/n\) also preserves every weighted sum, so the argument does not rely on treating identical records as different types.
The equality
\[
\sum_{t:\,c\in A_t,\ A_t\cap W=\varnothing}\mu_t
=
\frac{|U_c(W)|}{n}
\]
is correct. Consequently, the target’s strict inequality is equivalent to \(|U_c(W)|<n/k\), exactly the negation of a justified-representation violation.
There are at most \(n\) output types, and \(1/n\) has polynomial encoding length. Compatibility, candidate identities, and \(k\) are unchanged.
With \(F\) and \(Y\) explicitly represented, a rational committee certificate can be checked by enumeration and exact rational summation in polynomial time.
The global collection of rational approval-interval endpoints partitions \(\mathbb R\) into cells on which, for each facility, every type’s approval status is constant. Moving selected locations within the same open cell therefore preserves all approval relations. Assigning distinct rational interior points preserves the no-co-location constraint and gives polynomial-size certificates.
After identifying the types unrepresented by \(W\), the mass associated with \((f,y)\) is the weighted depth at \(y\) of their intervals for facility \(f\). A sweep over rational endpoints computes its maximum in polynomial time. Candidates in \(W\) need not be excluded separately because every unrepresented type fails to approve each member of \(W\).
The only gap is an encoding clarification. The reduction assigns \(x_{t_i}=x_i\) and \(r_{t_if}=r_{if}\), but the quoted known result, as reproduced in the task, does not explicitly state that its hard instances use rational agent locations and a rational common radius. The prover later calls that radius rational without justifying this from the stated theorem. The minimum required repair is to state or cite the precise restricted hardness theorem guaranteeing rationally encoded locations and radii. Under the usual rational encoding implicitly invoked by the prover, this is expositional rather than a substantive mathematical defect.
⟨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.