Answer: \(\mathrm{NP}\)-hard, even for \(\tau=2\) on trees with strictly positive integer capacities and \(R+B=\sum_v q_v\).
Theorem 3.3 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateThe following problem is NP-complete: Given a Schelling instance and a rational number s, decide whether there exists an assignment with social welfare at least s. The hardness holds even for the class of instances where the number of agents is equal to the number of nodes and the topology is a regular graph.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite graph \(G=(V,E)\), rational capacities \(q_v\ge 0\), rational total masses \(R,B\), and a rational threshold \(s\), does there exist a real allocation \(x_{v,c}\ge 0\) with \(x_{v,R}+x_{v,B}\le q_v\), \(\sum_v x_{v,R}=R\), and \(\sum_v x_{v,B}=B\), such that \(W(x)\ge s\)? For each \(v\) and \(c\in\{R,B\}\), define \(u_{v,c}(x)=\frac{\sum_{w\in N(v)}x_{w,c}}{\sum_{w\in N(v)}(x_{w,R}+x_{w,B})}\), with value \(0\) when the denominator is \(0\), and let \(W(x)=\sum_{v,c}x_{v,c}u_{v,c}(x)\).
Let \(G=(V,E)\) be a finite simple connected undirected graph with \(m=|V|\ge2\), and let \(N(v)\) be its open neighborhood. Input capacities are \(q_v\in\mathbb Q_{\ge0}\), and the threshold is \(s\in\mathbb Q\).
A society is given by its support: the list of the \(\tau\) types with positive mass, each mass a binary rational. Here the possible types are red and blue, with masses \(R,B\in\mathbb Q_{\ge0}\), absent types having mass zero; \(\tau\) is the support size, not the number of possible types. Assume \(0<R+B\le\sum_v q_v\); masses are not normalized to sum to one.
An allocation consists of real \(x_{v,c}\ge0\) for \(c\in\{R,B\}\), satisfying \(x_{v,R}+x_{v,B}\le q_v\), \(\sum_v x_{v,R}=R\), and \(\sum_v x_{v,B}=B\). Both types may occupy the same vertex, and capacity may remain unused.
Define \(u_{v,c}(x)=\frac{\sum_{w\in N(v)}x_{w,c}}{\sum_{w\in N(v)}(x_{w,R}+x_{w,B})}\) when the denominator is positive, and \(u_{v,c}(x)=0\) otherwise. Set \(W(x)=\sum_{v\in V}\sum_{c\in\{R,B\}}x_{v,c}u_{v,c}(x)\).
Let \(L\) be the total binary input length; state running times in \(m,\tau,L\).
Is deciding whether there exists a feasible real allocation \(x\) with \(W(x)\ge s\) in \(\mathrm P\), or is it \(\mathrm{NP}\)-hard?
For indivisible agents occupying distinct vertices, this welfare-threshold problem is NP-complete even on regular graphs with every vertex occupied ([source](https://arxiv.org/pdf/2012.02086)). Computing maximum welfare is also NP-hard on cubic graphs ([source](https://arxiv.org/abs/2201.06904)).
No complexity result for exactly the real mass-allocation problem defined above was located in the literature search.
The decision problem is \(\mathrm{NP}\)-hard, even when \(\tau=2\), the graph is a tree, every capacity is a strictly positive integer, and \(R+B=\sum_v q_v\).
The reduction below controls all feasible real allocations; it does not assume that vertices are monochromatic.
Use the standard NP-complete problem PARTITION: given positive integers \(a_1,\ldots,a_n\), encoded in binary, decide whether some \(S\subseteq\{1,\ldots,n\}\) satisfies
\(\displaystyle 2\sum_{i\in S}a_i=\sum_{i=1}^n a_i.\)
This is one of the classical problems in [Karp’s NP-completeness theorem](https://link.springer.com/chapter/10.1007/978-1-4684-2001-2_9).
Set
\(\displaystyle A=\sum_{i=1}^n a_i,\qquad D=4(n+1),\qquad c_i=Da_i.\)
Construct a tree with vertices \(h,u_1,v_1,\ldots,u_n,v_n\) and edges \(hu_i,u_iv_i\) for every \(i\). Thus \(m=2n+1\). Assign capacities
\(\displaystyle q_h=1,\qquad q_{u_i}=q_{v_i}=c_i.\)
Choose the two positive masses and threshold as follows:
\(\displaystyle R=B=DA+\frac12,\qquad T=R+B=2DA+1,\qquad s=T-(n+1).\)
All capacities are strictly positive integers. Also, \(T=\sum_vq_v\), so every feasible allocation saturates every vertex: the nonnegative quantities \(q_v-x_{v,R}-x_{v,B}\) sum to zero.
Write \(r_v=x_{v,R}\) and \(b_v=x_{v,B}=q_v-r_v\). Define the welfare loss by \(\mathcal L(x)=T-W(x)\). The threshold condition is precisely \(\mathcal L(x)\le n+1\).
For a saturated allocation, let \(d_v=\sum_{w\in N(v)}q_w\). Every \(d_v\) is positive in the constructed tree.
The loss at vertex \(v\) is
\(\displaystyle q_v-\frac{r_v\sum_{w\in N(v)}r_w+b_v\sum_{w\in N(v)}b_w}{d_v} =\frac{r_v\sum_{w\in N(v)}b_w+b_v\sum_{w\in N(v)}r_w}{d_v}.\)
Here the equality follows by expanding \(q_vd_v=(r_v+b_v)\sum_{w\in N(v)}(r_w+b_w)\).
Summing and collecting the two contributions of each undirected edge gives
\(\displaystyle \mathcal L(x)=\sum_{\{v,w\}\in E}\left(\frac1{d_v}+\frac1{d_w}\right)(r_vb_w+b_vr_w).\)
Every summand is nonnegative.
For branch \(i\), define
\(\displaystyle y_i=r_{u_i}+r_{v_i},\qquad z_i=\frac{y_i}{2c_i},\qquad \delta_i=\min\{y_i,2c_i-y_i\}.\)
Thus \(\delta_i\) measures the distance of the branch’s red mass from either zero or its full capacity.
We have \(d_{u_i}=c_i+1\) and \(d_{v_i}=c_i\). Moreover,
\(\displaystyle r_{u_i}b_{v_i}+b_{u_i}r_{v_i} =c_i y_i-2r_{u_i}r_{v_i} \ge c_i y_i-\frac{y_i^2}{2} =2c_i^2z_i(1-z_i),\)
where the inequality uses \(r_{u_i}r_{v_i}\le y_i^2/4\).
Consequently, the loss contributed by edge \(u_iv_i\) is at least
\(\displaystyle \frac1{c_i}\,2c_i^2z_i(1-z_i) \ge c_i\min\{z_i,1-z_i\} =\frac{\delta_i}{2}.\)
The second inequality holds because \(2z(1-z)\ge\min\{z,1-z\}\) for \(0\le z\le1\). Discarding the other nonnegative edge contributions proves the key bound
\(\displaystyle \sum_{i=1}^n\delta_i\le2\mathcal L(x).\)
Suppose \(S\) is a partition witness. Fill both vertices of branch \(i\) entirely with red when \(i\in S\), and entirely with blue otherwise. At \(h\), place red and blue mass \(1/2\) each.
The branch red mass is \(2D\sum_{i\in S}a_i=DA\), so both prescribed type totals are satisfied.
Each leaf \(v_i\) has utility one for its occupying type and contributes zero loss. At \(u_i\), the same-type neighboring mass is \(c_i+1/2\), while total neighboring mass is \(c_i+1\). Its loss is therefore \(c_i/[2(c_i+1)]\).
The neighbors of \(h\) contain red and blue mass \(DA/2\) each. Both utilities at \(h\) equal \(1/2\), giving hub loss \(1/2\). Hence
\(\displaystyle \mathcal L(x)=\frac12+\sum_{i=1}^n\frac{c_i}{2(c_i+1)} \le\frac{n+1}{2}<n+1.\)
Thus \(W(x)\ge s\).
Conversely, consider any feasible real allocation. Round its branches by defining
\(\displaystyle S=\{i:y_i\ge c_i\}.\)
By the definition of \(\delta_i\),
\(\displaystyle \left|y_i-2c_i\mathbf1_{\{i\in S\}}\right|=\delta_i.\)
The total red-mass constraint gives
\(\displaystyle \sum_i y_i=DA+\frac12-r_h,\qquad 0\le r_h\le1.\)
The triangle inequality and the key bound therefore imply
\(\displaystyle \left|DA-2D\sum_{i\in S}a_i\right| \le\left|r_h-\frac12\right|+\sum_i\delta_i \le\frac12+2\mathcal L(x). \)
If the PARTITION instance is a no-instance, the integer \(A-2\sum_{i\in S}a_i\) is nonzero, so its absolute value is at least one. It follows that
\(\displaystyle \mathcal L(x)\ge\frac D2-\frac14 =2(n+1)-\frac14>n+1. \)
Thus no feasible real allocation meets the welfare threshold in a no-instance. Together with the preceding section, this proves the required equivalence.
Let \(\ell\) denote the binary length of the PARTITION instance. The reduction produces \(m=2n+1\), \(\tau=2\), and output length \(L=O(\ell+n\log(n+1))\). It can be computed in \(O(\ell^2)\) bit operations using elementary integer arithmetic.
Therefore, an algorithm polynomial in \(m,\tau,L\) for the stated problem would imply \(\mathrm P=\mathrm{NP}\). The reduction establishes NP-hardness, without asserting strong NP-hardness.
For comparison, the case \(\tau=1\) is polynomial-time solvable. Let \(M\) be the sole positive mass and define
\(\displaystyle U=\{v:q_v>0\text{ and some }w\in N(v)\text{ has }q_w>0\},\qquad C=\sum_{v\in U}q_v.\)
Vertices outside \(U\) always contribute zero welfare, so \(W\le\min\{M,C\}\). This bound is attained:
Thus the one-type answer is yes exactly when \(s\le\min\{M,C\}\). Scanning the graph and performing exact rational additions and comparisons takes, conservatively, \(O(m^2+mL^2)\) bit operations.
⟨structured verdict parsed — rendered above⟩
The output proves the claimed \(\mathrm{NP}\)-hardness result. The reduction applies to all feasible real allocations, including allocations that mix both types at individual vertices. I found no major or minor mathematical issues.
The prover states the relevant source problem precisely: PARTITION on binary-encoded positive integers, with acceptance condition \(2\sum_{i\in S}a_i=A\). Its cited NP-completeness result is the standard one attributed to [Karp](https://link.springer.com/chapter/10.1007/978-1-4684-2001-2_9).
For a nonempty source instance, the constructed graph is simple, connected, and acyclic, with \(m=2n+1\ge3\). All capacities are positive integers because \(D=4(n+1)>0\) and \(a_i>0\). Both masses are positive binary rationals, so \(\tau=2\).
The capacity sum is exactly
\(\sum_vq_v=1+2\sum_iDa_i=2DA+1=R+B\).
Thus the construction satisfies the task’s input promise. The saturation argument is valid: every capacity slack is nonnegative, and their sum is zero, forcing each slack to vanish. Consequently, \(b_v=q_v-r_v\) holds for every feasible allocation.
Saturation makes every neighborhood denominator equal to \(d_v=\sum_{w\in N(v)}q_w\). These denominators are positive because every constructed vertex has a neighbor of positive capacity. The zero-denominator convention therefore creates no exceptional case.
The displayed vertex-loss identity correctly expands \(q_vd_v\) and subtracts the same-type terms. Collecting the two directed contributions of each undirected edge gives exactly the stated coefficient \(1/d_v+1/d_w\). No contribution is omitted or counted twice. Every resulting summand is nonnegative.
Capacity constraints imply \(0\le y_i\le2c_i\), hence \(0\le z_i\le1\). The identity
\(r_{u_i}b_{v_i}+b_{u_i}r_{v_i}=c_iy_i-2r_{u_i}r_{v_i}\)
is correct. The bound \(r_{u_i}r_{v_i}\le y_i^2/4\) applies to all permitted real values and yields the displayed lower bound.
The edge coefficient is \(1/(c_i+1)+1/c_i\), so retaining only \(1/c_i\) gives a valid lower bound. The inequality \(2z(1-z)\ge\min\{z,1-z\}\) holds throughout the specified interval, including its endpoints and midpoint. Finally,
\(c_i\min\{z_i,1-z_i\}=\delta_i/2\).
Therefore \(\sum_i\delta_i\le2\mathcal L(x)\) follows exactly as written. This is the essential step addressing continuous allocations; it does not presume monochromatic vertices.
The proposed allocation respects every capacity. Its branch red mass is \(DA\), and the hub adds \(1/2\), giving the required red total; the blue total is likewise correct.
Each leaf has utility one for its occupying type. Each \(u_i\) has the stated loss \(c_i/[2(c_i+1)]\). At the hub, the red and blue neighboring masses are each \(DA/2\), so its total loss is \(1/2\).
Thus the loss calculation and bound are correct:
\(\mathcal L(x)\le(n+1)/2<n+1\).
The allocation meets the threshold.
The rounding definition handles ties correctly: when \(y_i=c_i\), either endpoint is at distance \(c_i=\delta_i\), and the chosen convention preserves the displayed identity.
The red-mass constraint gives
\(\sum_i y_i=DA+1/2-r_h\), with \(0\le r_h\le1\).
Applying the triangle inequality to the branch-rounding errors therefore yields the stated discrepancy bound
\(\left|DA-2D\sum_{i\in S}a_i\right|\le1/2+2\mathcal L(x)\).
For a no-instance, \(A-2\sum_{i\in S}a_i\) is a nonzero integer for every subset \(S\), including the subset obtained by rounding. Hence the discrepancy is at least \(D\), and
\(\mathcal L(x)\ge D/2-1/4=2(n+1)-1/4>n+1\).
The constants and strict inequality are correct. This excludes every feasible real allocation in a no-instance.
The construction uses binary arithmetic; it never expands a capacity into individual agents. Scaling by \(D\) adds only \(O(\log(n+1))\) bits per capacity. The graph encoding, masses, and threshold fit the stated bound \(L=O(\ell+n\log(n+1))\).
The conservative construction time \(O(\ell^2)\) is sufficient for elementary integer arithmetic and writing the output. Thus this is a polynomial-time many-one reduction. The conclusion about algorithms polynomial in \(m,\tau,L\) follows. Neither membership in \(\mathrm{NP}\) nor strong NP-hardness is asserted or required.
Vertices outside \(U\) contribute zero welfare: they either have zero capacity or have no neighbor capable of holding positive mass. Hence \(W\le\min\{M,C\}\).
The constructions attain this bound. In the proportional allocation, every vertex of \(U\) has a neighbor in \(U\) receiving positive mass. When \(M>C\), filling \(U\) preserves those occupied neighbors, and the remaining capacity outside \(U\) suffices. The case \(C=0\) correctly gives welfare zero.
The exact threshold criterion and the conservative running time \(O(m^2+mL^2)\) are valid for binary rational inputs.
No repair or additional clarification is needed. The output resolves the requested complexity classification.
⟨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.