Answer: \(\mathrm{NP}\)-complete, even for \(\tau=1\), \(m=n\), and graphs of maximum degree \(3\), under standard explicit graph encoding.
Proposition 1 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateGiven an instance (G, O, ν) and a number t, decid- ing if an allocation π such that Extπ(G) ≥t exists is NP-complete, even if the valuations are 0 or 1.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a graph \(G=(V,E)\) with \(n=|V|\), rational \(\alpha\in[0,1]\), and rational threshold \(\theta\), decide whether there is a distribution \(p\) over subsets \(S\subseteq V\) such that \(\sum_S p_S=1\), \(\sum_S p_S|S|=n\alpha\), and \(\sum_S p_S e_G(S)\ge n\theta\), where \(e_G(S)=|\{v\in V\setminus S:N_G(v)\cap S\ne\varnothing\}|\). Interpret \(p\) as the mass of page copies using each integral placement, with high-valued items on \(S\), and maximize average externality across the continuous population of copies.
Let \(G=(V,E)\) be a finite simple undirected graph with \(n=|V|\ge1\), and let \(m=n\) be the number of objects on each copy. The input includes binary rationals \(\alpha\in[0,1]\) and \(\theta\in\mathbb Q\).
A society is given by its support: the list of the \(\tau\) types with positive mass, each with its mass as a binary rational; \(\tau\) is the support size, not the number of possible types. Here the input society consists of one type of identical graph copies, of total mass \(1\), so \(\tau=1\).
On each copy, a placement \(S\subseteq V\) gives value \(1\) to vertices in \(S\) and value \(0\) to all other vertices; every vertex receives exactly one object. Its externality is \(e_G(S)=|\{v\in V\setminus S:N_G(v)\cap S\ne\varnothing\}|\), where \(N_G(v)\) is the open neighborhood.
A feasible allocation splits the population among placements using nonnegative rational masses \(p_S\), subject to \(\sum_{S\subseteq V}p_S=1\) and \(\sum_{S\subseteq V}p_S|S|=n\alpha\). Placements and their support are chosen by the allocation, not supplied or restricted in the input; individual copies need not have the same number of value-\(1\) objects.
Decide whether a feasible allocation satisfies \(\sum_{S\subseteq V}p_Se_G(S)\ge n\theta\). Let \(L\) be the total binary input length; state running times in \(m,n,\tau,L\).
Is this continuous allocation decision problem in \(\mathrm P\), or is it \(\mathrm{NP}\)-hard?
The discrete problem, with exactly \(k\) value-\(1\) objects and \(n-k\) value-\(0\) objects on one graph, is \(\mathrm{NP}\)-complete, even on graphs of maximum degree \(3\). [Discrete result](https://journals.sagepub.com/doi/10.3233/FAIA200082).
No result settling this exact distributional problem was identified in the literature search.
The continuous allocation decision problem is \(\mathrm{NP}\)-complete under the standard explicit encoding of graphs. Hardness holds even when \(\tau=1\), \(m=n\), and \(G\) has maximum degree \(3\).
The key is to choose a threshold at which every placement with positive mass must be a dominating set.
A set \(D\subseteq V\) is a dominating set if every vertex in \(V\setminus D\) has a neighbor in \(D\). Write \(\gamma(G)\) for the minimum cardinality of a dominating set.
For any placement \(S\subseteq V\), define its number of undominated vertices outside \(S\) by
\[ u_G(S)=|\{v\in V\setminus S:N_G(v)\cap S=\varnothing\}|. \]
The vertices outside \(S\) partition into those counted by \(e_G(S)\) and those counted by \(u_G(S)\). Hence
\[ e_G(S)=n-|S|-u_G(S). \]
Consequently, every feasible allocation satisfies
\[ \sum_Sp_Se_G(S) =n-n\alpha-\sum_Sp_Su_G(S) \le n(1-\alpha). \]
Moreover, equality holds if and only if every placement with positive mass is a dominating set. Indeed, every summand \(p_Su_G(S)\) is nonnegative, so their sum is zero exactly when \(u_G(S)=0\) for every \(S\) with \(p_S>0\).
We use the known theorem that Dominating Set is \(\mathrm{NP}\)-complete even on finite simple planar graphs of maximum degree \(3\): given \(G\) and an integer \(k\), decide whether \(\gamma(G)\le k\). This is the restriction recorded in [Garey–Johnson, problem GT2](https://perso.limos.fr/~palafour/PAPERS/PDF/Garey-Johnson79.pdf).
Restrict to instances with \(n\ge1\) and \(0\le k\le n\); instances outside these bounds are trivial. Construct the allocation instance using the same graph and set
\[ m=n,\qquad \tau=1,\qquad \alpha=\frac{k}{n},\qquad \theta=\frac{n-k}{n}. \]
These are valid binary rationals of encoding length \(O(\log(n+1))\). We prove
\[ \gamma(G)\le k \quad\Longleftrightarrow\quad \text{the constructed allocation instance is a yes-instance}. \]
Forward implication. Suppose \(D\) is a dominating set with \(|D|\le k\). Since \(k\le n\), extend \(D\) to a set \(S\) of cardinality exactly \(k\). A superset of a dominating set is dominating: every vertex outside \(S\) is outside \(D\) and has a neighbor in \(D\subseteq S\).
Put all population mass on \(S\). Then
\[ \sum_Tp_T|T|=k=n\alpha, \qquad \sum_Tp_Te_G(T)=e_G(S)=n-k=n\theta. \]
Thus the allocation is feasible and meets the threshold.
Reverse implication. Suppose a feasible allocation meets the threshold. Section 1 gives
\[ n-k \le \sum_Sp_Se_G(S) =n-k-\sum_Sp_Su_G(S) \le n-k. \]
Therefore every positive-mass placement is a dominating set. Its average cardinality is \(k\). At least one positive-mass placement has cardinality at most \(k\), since otherwise their average would exceed \(k\). That placement witnesses \(\gamma(G)\le k\).
The reduction preserves the graph, including planarity and maximum degree. It takes polynomial time in the source input length. This proves \(\mathrm{NP}\)-hardness for the exact distributional problem, with unrestricted placement support.
We next prove membership in \(\mathrm{NP}\), including the rational-certificate requirement.
Put \(b=n\alpha\). Temporarily allow real masses and consider
\[ P_b= \left\{ p\in\mathbb R_{\ge0}^{2^n}: \sum_Sp_S=1,\quad \sum_Sp_S|S|=b \right\}. \]
This set is nonempty: masses \(1-\alpha\) on \(\varnothing\) and \(\alpha\) on \(V\) are feasible. It is closed and bounded, so the linear objective \(\sum_Sp_Se_G(S)\) attains a maximum.
Choose an optimizer having minimum support cardinality. Suppose its support contains at least three placements. The vectors \((1,|S|)\) indexed by that support are linearly dependent in \(\mathbb R^2\). Thus there is a nonzero vector \(d\), supported there, satisfying
\[ \sum_Sd_S=0,\qquad \sum_Sd_S|S|=0. \]
Both \(p+td\) and \(p-td\) are feasible for sufficiently small positive \(t\), because all coordinates in the support of \(d\) initially have positive mass. Optimality therefore forces
\[ \sum_Sd_Se_G(S)=0; \]
otherwise one of these two perturbations would improve the objective.
Since \(d\ne0\) and \(\sum_Sd_S=0\), some coordinate of \(d\) is negative. Take
\[ t_*=\min_{d_S<0}\frac{p_S}{-d_S}. \]
Then \(p+t_*d\) is feasible, has the same objective, and has strictly smaller support. This contradicts the choice of \(p\). Hence an optimizer uses at most two placements.
If two supported placements have equal cardinality, putting all their mass on the one with greater externality preserves feasibility and does not decrease the objective. Otherwise, let their cardinalities be \(a<c\). Their masses are necessarily
\[ p_A=\frac{c-b}{c-a}, \qquad p_C=\frac{b-a}{c-a}. \]
Because \(b=n\alpha\) is rational, these masses are rational and have binary encoding length \(O(L+\log(n+1))\). A one-placement optimizer has mass \(1\).
Thus the real optimum is attained by a rational allocation using at most two placements. Every yes-instance consequently has a certificate consisting of two vertex subsets and polynomial-length rational masses. A verifier computes their cardinalities and externalities and checks all constraints using exact rational arithmetic.
Under explicit graph encoding, the certificate length and verification time are polynomial in \(L\). Therefore the problem belongs to \(\mathrm{NP}\).
For completeness, define
\[ F_j=\max_{\substack{S\subseteq V\\|S|=j}}e_G(S), \qquad 0\le j\le n. \]
Enumerating every subset computes all \(F_j\) using \(O(2^n(n+|E|))\) elementary graph operations.
By Section 3, the optimum is the largest of:
Every listed candidate is attainable by choosing placements realizing the corresponding \(F_j\). Conversely, every optimal allocation has at most two placements and is bounded by one of these candidates. Thus this calculation is exact.
There are \(O(n^2)\) candidates, requiring exact arithmetic on numbers of bit length \(O(L+\log(n+1))\). The resulting deterministic running time is
\[ 2^n\operatorname{poly}(m,n,\tau,L), \qquad m=n,\quad \tau=1. \]
Certificate verification takes \(\operatorname{poly}(m,n,\tau,L)\) time. A deterministic algorithm polynomial in \(m,n,\tau,L\) for all these instances would imply \(\mathrm P=\mathrm{NP}\), since the reduction already fixes \(\tau=1\) and \(m=n\).
⟨structured verdict parsed — rendered above⟩
The prover resolves the target correctly. The reduction establishes \(\mathrm{NP}\)-hardness for the exact distributional problem, and the certificate argument establishes membership in \(\mathrm{NP}\). No major or minor mathematical issues were found.
1. Externality bound and its equality condition
The definition of \(u_G(S)\) counts exactly the vertices outside \(S\) that are not counted by \(e_G(S)\). Thus
\(e_G(S)=n-|S|-u_G(S)\)
holds for every placement, including \(S=\varnothing\) and \(S=V\).
Summing this identity against feasible masses correctly gives
\(\sum_S p_Se_G(S)=n-n\alpha-\sum_Sp_Su_G(S)\).
Both feasibility constraints are used correctly.
Every term \(p_Su_G(S)\) is nonnegative. There are finitely many placements, so equality in the upper bound holds exactly when every positive-mass placement has \(u_G(S)=0\). This is precisely the stated definition of a dominating set. No assumption about connectedness or the absence of isolated vertices is needed.
2. Source theorem and reduction
The cited source theorem is stated precisely enough for this application: Dominating Set remains \(\mathrm{NP}\)-complete on planar graphs of maximum degree three. The GT2 entry confirms both the “size at most \(k\)” formulation and the graph restriction. [Garey–Johnson, GT2](https://perso.limos.fr/~palafour/PAPERS/PDF/Garey-Johnson79.pdf).
The restriction to \(n\geq1\) and \(0\leq k\leq n\) does not undermine hardness. The cited source already uses positive \(k\leq n\); including \(k=0\) merely adds an easily decided case.
The constructed instance satisfies the target’s requirements:
The construction therefore has polynomial output length and takes polynomial time under the stated explicit graph encoding.
3. Forward implication
If \(D\) dominates and \(|D|\leq k\leq n\), extending it to cardinality exactly \(k\) is possible. The explanation that domination is preserved by taking a superset is correct: every vertex outside the larger set still has a neighbor in \(D\).
Putting mass one on that placement gives expected cardinality \(k=n\alpha\) and externality \(n-k=n\theta\). The mass is rational, so this witnesses feasibility in the original problem, not merely in its real relaxation.
4. Reverse implication
For the constructed threshold, the required externality equals the universal upper bound. The displayed chain of inequalities therefore forces
\(\sum_Sp_Su_G(S)=0\).
By the already verified equality characterization, every supported placement dominates.
The support is nonempty because its masses sum to one. If every supported placement had cardinality greater than \(k\), their finite weighted average would also exceed \(k\), contradicting feasibility. Hence a supported dominating set has cardinality at most \(k\).
This argument correctly accommodates unrestricted support and varying cardinalities across copies. It does not assume the discrete cardinality constraint that the task explicitly excludes.
The endpoints also work: \(k=0\) forces the empty placement, which cannot dominate a nonempty graph; \(k=n\) admits the placement \(V\).
5. Existence of an optimizer with at most two placements
The real feasible set is nonempty, closed, and bounded in a finite-dimensional space. Its linear objective consequently attains a maximum. Choosing an optimizer of minimum support cardinality is legitimate because support cardinalities are integers between one and \(2^n\).
For support size at least three, the vectors \((1,|S|)\) are linearly dependent. The resulting nonzero direction preserves both equality constraints. Small perturbations in either direction preserve nonnegativity because every coordinate on which the direction is supported initially has positive mass.
Optimality then forces zero objective change along that direction; otherwise one of the two perturbations would improve the objective.
The condition \(\sum_Sd_S=0\), together with \(d\neq0\), guarantees a negative coordinate. The specified \(t_*\) is positive and finite. At this value, no coordinate becomes negative, at least one supported coordinate becomes zero, and no previously unsupported coordinate becomes positive. Thus support strictly decreases without changing feasibility or objective. The contradiction proves the claim.
6. Rational certificates and membership in \(\mathrm{NP}\)
If two placements have equal cardinality, replacing the mixture by the placement with greater externality preserves feasibility and does not decrease the objective.
For distinct cardinalities \(a<c\), the stated masses follow correctly from normalization and the mean-cardinality constraint. Nonnegativity follows from feasibility, which places \(b\) between \(a\) and \(c\).
Their encoding-length bound is valid: forming \(b=n\alpha\), subtracting integers of magnitude at most \(n\), and dividing by \(c-a\) increases the rational bit length by only \(O(\log(n+1))\).
Consequently, every yes-instance has a rational witness using at most two placements. The verifier can check nonnegativity, normalization, expected cardinality, and the externality threshold using exact rational arithmetic in polynomial time. Under the explicitly stated graph encoding, the subsets themselves also have polynomial length in \(L\).
This establishes membership in \(\mathrm{NP}\) for the original rational allocation problem.
7. Exact algorithm and running times
Every \(F_j\) is well-defined because there is a subset of every cardinality from zero through \(n\). Enumerating subsets and scanning vertices and edges gives the stated bound on elementary graph operations.
The candidate formulas correctly represent one-placement allocations and mixtures of placements achieving \(F_a\) and \(F_c\). Conversely, the two-placement optimizer proved earlier cannot exceed the corresponding candidate. Thus the maximum over the listed candidates is exact.
There are \(O(n^2)\) candidate pairs, and their rational arithmetic has polynomial bit complexity. The overall bound
\(2^n\operatorname{poly}(m,n,\tau,L)\),
with \(m=n\) and \(\tau=1\), is valid. Certificate verification has the stated polynomial bound.
Repair feedback
None is required. The proof establishes \(\mathrm{NP}\)-completeness under its stated explicit encoding, including the maximum-degree-three restriction. Its conditional statement that a polynomial-time algorithm would imply \(\mathrm P=\mathrm{NP}\) is also correct.
⟨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.