Answer: \(\mathrm{NP}\text{-hard}\); the rational-threshold decision version is \(\mathrm{NP}\text{-complete}\).
Theorem 3.3 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateIt is NP-hard to find a set 𝑆 of 𝑘 nodes in the cluster graph to maximize the payoff 𝜋(𝑆), even when the cluster graph is unweighted. To prove the theorem, we first state a well-known property of any undirected graph. Denote the number of edges with at least one endpoint in 𝑆 by #𝑖𝑛𝑐𝑖𝑑𝑒𝑛𝑡(𝑆), the sum of the degrees of the nodes in 𝑆 by 𝐷𝑒𝑔𝑟𝑒𝑒𝑆𝑢𝑚(𝑆), and the number of edges in the subgraph induced by 𝑆 by #𝑖𝑛𝑑𝑢𝑐𝑒𝑑(𝑆). Furthermore, 𝑑𝑒𝑔𝑟𝑒𝑒(𝑣) denotes the degree of a node 𝑣.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite simple graph \(H=(V,E)\), positive rational masses \(a_v\) for accepting-community types and \(b_e\) for rejecting-boundary types, with \(\sum_{v\in V}a_v+\sum_{e\in E}b_e=1\), and a budget \(k\le |V|\), choose exactly \(k\) communities to seed, one seed per chosen community, to maximize \(\Pi(S)=\sum_{v\in S}a_v-\sum_{e\in E:\,e\cap S\ne\varnothing}b_e\).
Let \(H=(V,E)\) be a finite simple undirected graph, with \(m=|V|\geq 1\). Each vertex represents an accepting community; each edge represents a rejecting boundary shared by exactly its two endpoint communities.
A society is given by its support: the list of its \(\tau=|V|+|E|\) types with positive masses, each encoded as a binary rational. Thus \(\tau\) is the support size, not the number of possible types. Vertex masses \(a_v>0\) and edge masses \(b_e>0\) satisfy \(\sum_{v\in V}a_v+\sum_{e\in E}b_e=1\). Let \(L\) be the total binary input length.
Given an integer budget \(0\leq k\leq m\), choose \(S\subseteq V\) with \(|S|=k\), placing one seed in each chosen community. Seeding reaches that community's entire accepting mass and every incident rejecting boundary; rejecting boundaries do not propagate, and each boundary's mass is charged once. Seeds and community selections are indivisible.
The objective is to maximize \(\Pi(S)=\sum_{v\in S}a_v-\sum_{e\in E:\,e\cap S\neq\varnothing}b_e\).
Is exact maximization of \(\Pi(S)\) solvable in polynomial time in \(m,\tau,L\), with \(k\) part of the input, or is it NP-hard?
For the discrete version with unit vertex rewards and unit edge costs, maximizing payoff over exactly \(k\) selected communities is NP-hard, even on unweighted cluster graphs. The supplied result states no separate complexity classification for normalized rational-mass societies.
Exact maximization is \(\mathrm{NP}\)-hard. Its rational-threshold decision version is \(\mathrm{NP}\)-complete. The hardness holds even when every mass is a positive dyadic rational, so either interpretation of “binary rational” is covered.
The supplied claim about unit weights on cluster graphs is problematic under the stated objective. The proof below establishes hardness independently.
We use the standard \(\mathrm{NP}\)-completeness of CLIQUE: given a finite simple graph and an integer \(k\), decide whether it contains \(k\) pairwise adjacent vertices. See [Karp’s original paper](https://link.springer.com/chapter/10.1007/978-1-4684-2001-2_9). We may restrict to \(2\leq k\leq n\), where \(n\) is the number of vertices: excluded cases are directly decidable and can be mapped to fixed yes or no instances within this restriction.
Let \(G=(U,F)\) be such an instance, with \(n=|U|\) and \(q=|F|\).
Let \(M\) be the smallest power of two satisfying \(M\geq n\). Construct \(H=(V,E)\) by adding \(M-n\) isolated vertices to \(G\). Thus \(m=M<2n\), and \(E=F\).
Let \(Q\) be the smallest power of two satisfying \(Q\geq M+3q\), and define
\(\displaystyle c=\frac{Q-3q}{M}.\)
Since \(Q\geq M+3q\), we have \(c\geq1\). Writing \(d(v)\) for the degree of \(v\) in \(H\), assign masses
\(\displaystyle a_v=\frac{d(v)+c}{Q} =\frac{M d(v)+Q-3q}{MQ}, \qquad b_e=\frac1Q.\)
Every listed mass is strictly positive. Both denominators \(Q\) and \(MQ\) are powers of two, so every mass is dyadic.
The degree-sum identity gives \(\sum_{v\in V}d(v)=2q\). Consequently,
\(\displaystyle \sum_{v\in V}a_v+\sum_{e\in E}b_e =\frac{2q+Mc+q}{Q} =\frac{3q+(Q-3q)}{Q} =1. \)
Thus the construction satisfies the society’s normalization exactly. Preserve the budget \(k\).
For a set \(S\subseteq V\), define
\(\displaystyle E(S)=\{e\in E:e\subseteq S\},\qquad \delta(S)=\{e\in E:|e\cap S|=1\}.\)
An internal edge contributes twice to the sum of selected degrees; a crossing edge contributes once. Hence
\(\displaystyle \sum_{v\in S}d(v)=2|E(S)|+|\delta(S)|.\)
The edges charged by the objective are exactly \(E(S)\cup\delta(S)\), a disjoint union. Therefore, whenever \(|S|=k\),
\(\displaystyle \Pi(S) =\frac{\sum_{v\in S}d(v)+ck-|E(S)|-|\delta(S)|}{Q} =\frac{ck+|E(S)|}{Q}. \)
This identity uses precisely the requirement that each incident boundary is charged once.
Set the decision threshold to
\(\displaystyle T=\frac{ck+\binom{k}{2}}{Q}.\)
A simple graph on \(k\) vertices has at most \(\binom{k}{2}\) edges, with equality exactly when those vertices form a clique. The payoff identity therefore implies
\(\displaystyle \Pi(S)\geq T \quad\Longleftrightarrow\quad |E(S)|=\binom{k}{2} \quad\Longleftrightarrow\quad S\text{ is a clique}. \)
Since \(k\geq2\), such a clique cannot contain an added isolated vertex. Thus
\(\displaystyle G\text{ contains a clique of size }k \quad\Longleftrightarrow\quad \max_{|S|=k}\Pi(S)\geq T. \)
We have \(M<2n\), \(q\leq\binom n2\), and \(Q<2(M+3q)\). Thus all numerators and denominators above have \(O(\log n)\) binary bits, including those defining \(T\). The support contains exactly \(M+q\) types, and the construction has polynomial total encoding length.
An exact optimizer would therefore decide CLIQUE in polynomial time by computing its returned payoff and comparing it with \(T\). This proves the claimed \(\mathrm{NP}\)-hardness.
For a rational threshold \(T\), a certificate is a set \(S\) of exactly \(k\) vertices. Its size and incident edges can be checked directly, and \(\Pi(S)\) can be computed and compared with \(T\) using exact rational arithmetic.
To justify the bit complexity, take the product of all input denominators, including the threshold’s denominator, as a common denominator. Its binary length is at most the sum of their binary lengths. The resulting integer arithmetic therefore has polynomial bit complexity.
The decision version belongs to \(\mathrm{NP}\), and the reduction proves it is \(\mathrm{NP}\)-complete.
Normalization alone preserves any discrete instance’s optimizers: assigning \(a_v=b_e=1/\tau\) makes its payoff equal to the unit-weight payoff divided by \(\tau\).
However, the unit-weight problem on cluster graphs described here has a polynomial-time algorithm. A cluster graph is a disjoint union of cliques. In a clique of size \(t\), selecting exactly \(s\) vertices yields payoff
\(\displaystyle f_t(s)=s-\left[\binom t2-\binom{t-s}{2}\right],\qquad 0\leq s\leq t.\)
Indeed, the uncharged edges are exactly those between the \(t-s\) unselected vertices.
If the component sizes are \(t_1,\ldots,t_r\), let \(D_i(j)\) be the maximum payoff from selecting exactly \(j\) vertices in the first \(i\) components. Initialize \(D_0(0)=0\), with other states infeasible, and use
\(\displaystyle D_i(j)= \max_{0\leq s\leq\min(t_i,j)} \bigl[D_{i-1}(j-s)+f_{t_i}(s)\bigr], \)
omitting infeasible predecessor states. Every selection decomposes into component selections, and payoffs add across components, which proves the recurrence. There are polynomially many states and transitions because \(r,k,t_i\leq m\).
Consequently, the supplied cluster-graph hardness statement cannot hold for this exact model unless \(\mathrm{P}=\mathrm{NP}\). This discrepancy does not affect the independent hardness proof for normalized rational-mass societies.
⟨structured verdict parsed — rendered above⟩
The output resolves the target correctly: exact maximization is \(\mathrm{NP}\)-hard for normalized positive rational masses, including dyadic masses. Its rational-threshold decision version is \(\mathrm{NP}\)-complete. No major or minor mathematical issues were found.
The prover states the standard \(\mathrm{NP}\)-completeness theorem for CLIQUE with the appropriate graph and integer inputs, citing [Karp’s original paper](https://link.springer.com/chapter/10.1007/978-1-4684-2001-2_9). Restricting to \(2\leq k\leq n\) is valid: the excluded cases are directly decidable, and fixed yes and no instances exist within the restriction. The explanation is sufficient for this routine restriction.
Padding with isolated vertices preserves simplicity and leaves the original edges unchanged. The smallest power of two \(M\geq n\) satisfies \(n\leq M<2n\). Consequently, the preserved budget satisfies \(0\leq k\leq m=M\), as required.
From \(Q\geq M+3q\), the numerator \(Q-3q\) is at least \(M\), so \(c\geq1\). Every vertex mass is therefore strictly positive, as is every listed edge mass. Both \(Q\) and \(MQ\) are powers of two, establishing the claimed dyadic encoding. This remains valid when \(q=0\); there are then no edge types requiring masses.
The degree sum is \(2q\), and \(Mc=Q-3q\). The displayed total mass calculation is correct:
\(\sum_v a_v+\sum_e b_e=(2q+Mc+q)/Q=1\).
The support contains exactly \(M+q\) positive-mass types. Thus the construction respects the task’s definition of support size.
The definitions of internal and crossing edges give a disjoint partition of the charged edges. Selected degrees count internal edges twice and crossing edges once. Subtracting each charged edge once therefore gives
\(\Pi(S)=(ck+|E(S)|)/Q\)
for every feasible set of exactly \(k\) vertices. There is no double charging or omitted boundary cost.
Because \(Q>0\), comparison with the stated threshold is equivalent to
\(|E(S)|\geq\binom{k}{2}\).
Simplicity supplies the reverse bound, and equality characterizes a clique. Since \(k\geq2\), a qualifying clique cannot contain a padded isolated vertex. Both directions of the claimed equivalence with the original CLIQUE instance follow.
The proof does not require the threshold itself to be a mass or to lie in the interval of feasible payoffs. A threshold exceeding every feasible payoff correctly represents a no instance.
The bounds on \(M\), \(q\), and \(Q\) are correct. The mass numerators and denominators have \(O(\log n)\) bits. The threshold has the same bit bound: its numerator, when written over denominator \(MQ\), is polynomially bounded in \(n\).
There are \(O(n^2)\) support entries, and graph identifiers also require only polynomial total space. Constructing degrees, powers of two, masses, and the threshold takes polynomial time. Thus the argument establishes a polynomial reduction under the stated support encoding.
An exact optimizer supplies a maximizing set, whose payoff can be evaluated and compared with the threshold in polynomial time. The same conclusion holds if it returns the exact optimum value. Hence the reduction establishes the requested optimization hardness.
A certificate identifying exactly \(k\) distinct vertices has polynomial length. Its cardinality, incident edges, and payoff can be checked directly.
The common-denominator argument correctly controls arithmetic size: the product’s bit length is bounded by the sum of input denominator lengths, including the threshold denominator. Summation and comparison therefore take polynomial bit complexity. This also covers the allowed endpoint budgets \(k=0\) and \(k=m\). The claimed decision completeness follows.
Uniform normalization scales the unit-weight payoff by the positive factor \(1/\tau\), preserving optimizers.
The component payoff formula is correct because precisely the edges between unselected vertices remain uncharged. The dynamic-programming initialization and recurrence correctly enforce exact cardinality and componentwise additivity. There are polynomially many states and transitions, with polynomial-size integer payoffs.
Thus the supplied cluster-graph hardness statement conflicts with the stated objective unless \(\mathrm{P}=\mathrm{NP}\). The prover identifies this conflict accurately, and its independent reduction does not rely on that statement.
No repair or additional mathematical clarification is needed. The normalized rational-mass problem is settled by the independent reduction.
⟨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.