Answer: \(\mathrm{NP}\)-complete, even with fixed \(N=2\) for every fixed \(k\geq1\).
Theorem 2 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateLet k ≥1. Then, BestCoalition is NP- complete for the k-fold loyal variant of symmetric FOHGs.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite type set \(T\), rational masses \(\mu_t \geq 0\) summing to \(1\), a symmetric type-level friendship relation \(F\), a tagged representative of type \(a\), a loyalty depth \(k\), a reference population scale \(N\), and a rational normalized threshold \(q\), choose \(x_t \in [0,\mu_t]\). Let \(S=\{a\}\cup\{t:x_t>0\}\), and let \(v_b^N(x)=N\sum_{t:(b,t)\in F}x_t-\sum_{t:(b,t)\notin F}x_t\), with the tagged representative’s own mass omitted. Is there an \(x\) such that \(\min\{v_b^N(x): b\in S,\ d_{F[S]}(a,b)\leq k\}\geq q\)?
A nonatomic society is given by its support \(T\): the list of \(\tau=|T|\) types with positive binary-rational masses \(\mu_t\), where \(\sum_{t\in T}\mu_t=1\). Support size means the number of listed types, not the number of possible types.
The input also contains a symmetric relation \(F\subseteq T\times T\), a tagged representative of type \(a\in T\), binary-encoded integers \(k\geq1\) and \(N\geq1\), and a threshold \(q\in\mathbb Q\). Friendship gives weight \(N\), enmity weight \(-1\); diagonal entries of \(F\) specify friendship between distinct individuals of the same type.
The tagged representative has zero mass and must belong to the coalition. Choose real masses \(0\leq x_t\leq\mu_t\), and put \(S=\{a\}\cup\{t\in T:x_t>0\}\); the tagged singleton is allowed.
Define normalized utilities by \(v_b^N(x)=N\sum_{t:(b,t)\in F}x_t-\sum_{t:(b,t)\notin F}x_t\). An individual's own contribution is zero because individuals have zero mass; the remaining mass of its type is included.
Let \(F[S]\) be the undirected friendship graph on \(S\), ignoring loops, and define the tagged representative's loyal utility as \(U_a^k(x)=\min\{v_b^N(x):b\in S,\ d_{F[S]}(a,b)\leq k\}\), with disconnected distances infinite.
The decision problem asks whether some \(x\) satisfies \(U_a^k(x)\geq q\). Let \(L\) be the total input bit length; express running times in \(\tau,L,k,N\), distinguishing numerical values from encoding lengths. There is no independent alternative-count parameter \(m\) in this model.
Is this continuous loyal best-coalition decision problem in \(\mathrm P\), or is it \(\mathrm{NP}\)-hard?
For finite societies, best-coalition decision with symmetric friendship weights equal to the population size and enemy weights \(-1\) is \(\mathrm{NP}\)-complete for every fixed loyalty depth \(k\geq1\). [Bullinger and Kober](https://pub.dss.in.tum.de/brandt-research/loyal.pdf)
No result settling this exact nonatomic problem was located in the literature search.
The problem is \(\mathrm{NP}\)-complete. In fact, it remains \(\mathrm{NP}\)-complete with the constant friendship weight \(N=2\), for every fixed loyalty depth \(k\geq1\).
The reduction below uses dyadic masses, symmetric friendship, and exactly the treatment of diagonal entries specified in the question.
For \(q\leq0\), the tagged singleton is a feasible coalition. The hardness construction has \(q>0\).
For any \(S\subseteq T\) containing \(a\), define
\(B_k(S)=\{b\in S:d_{F[S]}(a,b)\leq k\}\).
Consider the rational linear feasibility problem consisting of
\(0\leq x_t\leq\mu_t\) for every \(t\in T\),
\(x_t=0\) for every \(t\notin S\),
and
\(v_b^N(x)\geq q\) for every \(b\in B_k(S)\).
Crucially, we do not require positive masses for all types in \(S\).
If this linear program is feasible, let its solution have actual support
\(S'=\{a\}\cup\{t:x_t>0\}\subseteq S\).
Every path in \(F[S']\) is also a path in \(F[S]\). Consequently,
\(B_k(S')\subseteq B_k(S)\).
Thus every utility required by the actual coalition is at least \(q\), so the solution is feasible for the original problem. Conversely, any feasible coalition satisfies the linear program for its actual support.
Hence the original instance is a yes-instance exactly when one of these linear programs is feasible.
Each program has \(\tau\) variables, \(O(\tau)\) constraints, and encoding length polynomial in \(\tau,L\). By polynomial-time solvability of rational linear feasibility, a certificate consisting only of \(S\) can be verified in polynomial time. Therefore the problem belongs to \(\mathrm{NP}\).
Enumerating all \(2^{\tau-1}\) sets containing \(a\) gives an exact deterministic algorithm with running time
\(2^{\tau-1}\operatorname{poly}(\tau,L)\).
The numerical value of \(k\) does not require iteration: breadth-first search computes distances, and \(k\) can be replaced by \(\min\{k,\tau-1\}\). Arithmetic involving \(N\) depends on its encoding length \(O(\log(N+1))\), not on \(N\) iterations. Both integer encoding lengths are included in \(L\).
Lemma. Let \(H\) be a nonempty simple graph, \(A\) its adjacency matrix, and \(\omega(H)\) its maximum clique size. For every vector \(p\geq0\) with \(\sum_i p_i=1\),
\(p^{\mathsf T}Ap\leq1-\frac1{\omega(H)}\).
Proof. Suppose two positive coordinates \(p_i,p_j\) correspond to nonadjacent vertices. Write \(z=Ap\).
Because \(A_{ii}=A_{jj}=A_{ij}=A_{ji}=0\), transferring mass between coordinates \(i,j\) leaves \(z_i,z_j\) unchanged. If \(z_i\geq z_j\), transfer all mass \(p_j\) to \(i\). The change in the quadratic form is
\(2p_j(z_i-z_j)\geq0\).
If \(z_j>z_i\), transfer all mass \(p_i\) to \(j\), again without decreasing the quadratic form.
Each transfer removes one vertex from the positive support. Repeating therefore produces a vector \(\widehat p\) whose positive support is a clique, while
\(p^{\mathsf T}Ap\leq\widehat p^{\mathsf T}A\widehat p\).
If that clique has \(c\) vertices, then
\(\widehat p^{\mathsf T}A\widehat p=1-\sum_i\widehat p_i^2\leq1-\frac1c\leq1-\frac1{\omega(H)}\).
The first inequality follows from \((\sum_i\widehat p_i)^2\leq c\sum_i\widehat p_i^2\). This proves the lemma.
We reduce from the standard \(\mathrm{NP}\)-complete Clique decision problem. Its \(\mathrm{NP}\)-completeness is established in [Karp’s original paper](https://link.springer.com/chapter/10.1007/978-1-4684-2001-2_9).
Take an instance consisting of a simple graph \(G\) on \(n\) vertices and a target \(r\), with \(2\leq r\leq n\).
Add \(2n\) new vertices that form a clique and are adjacent to every original vertex. Call the resulting graph \(H\), and put
\(h=|V(H)|=3n,\qquad R=r+2n\).
Then
\(\omega(H)=\omega(G)+2n\),
so \(G\) has a clique of size at least \(r\) exactly when \(H\) has a clique of size at least \(R\). We will also use
\(3R-2-2h=3r-2>0\).
Choose a power of two \(D\) satisfying \(D\geq2(3R+h)\), and set \(\delta=1/D\).
Create the types
\(T=\{a,b,c,z\}\cup V(H)\),
with masses
\(\mu_a=\mu_c=R\delta,\qquad \mu_b=(R-1)\delta,\)
\(\mu_v=\delta\quad(v\in V(H)),\)
\(\mu_z=1-(3R+h-1)\delta.\)
These masses sum to one. They are positive and dyadic; in particular, the choice of \(D\) gives \(\mu_z>1/2\).
The symmetric friendships are precisely:
All other pairs are enemies. Thus vertex types have enemy diagonals, and \(z\) is an enemy of every type.
Tag a representative of type \(a\), and set
\(N=2,\qquad q=(5R-2)\delta.\)
The construction works for any chosen depth \(k\geq1\).
Suppose a feasible coalition exists. Write
\(X=\sum_{v\in V(H)}x_v\).
If \(x_b=0\), the tagged representative’s utility is
\(v_a^2(x)=2x_a-x_c+2X-x_z\leq2R\delta+2h\delta.\)
But
\(q-(2R+2h)\delta=(3R-2-2h)\delta=(3r-2)\delta>0.\)
This contradicts \(v_a^2(x)\geq q\). Therefore \(x_b>0\).
Since \(a,b\) are friends, \(b\) lies at distance one from the tag and must satisfy \(v_b^2(x)\geq q\), for every \(k\geq1\).
The two required utilities are
\(v_a^2(x)=2x_a+2x_b-x_c+2X-x_z,\)
\(v_b^2(x)=2x_a+2x_b+2x_c-X-x_z.\)
Consequently,
\(3q\leq v_a^2(x)+2v_b^2(x)=6x_a+6x_b+3x_c-3x_z.\)
The capacity bounds give
\(6x_a+6x_b+3x_c-3x_z\leq6R\delta+6(R-1)\delta+3R\delta=3q.\)
Equality must hold throughout. Since each capacity deficit and \(x_z\) has a strictly positive coefficient in the difference from the upper bound, this forces
\(x_a=R\delta,\qquad x_b=(R-1)\delta,\qquad x_c=R\delta,\qquad x_z=0.\)
Moreover, both \(v_a^2(x)\) and \(v_b^2(x)\) equal \(q\). Substitution into the expression for \(v_a^2(x)\) yields
\((3R-2)\delta+2X=(5R-2)\delta,\)
hence
\(X=R\delta.\)
Let \(A\) be the adjacency matrix of \(H\), and write \(y=(x_v)_{v\in V(H)}\).
Every vertex type with positive mass is a friend of \(a\), so its utility is constrained for every \(k\geq1\).
For such a vertex \(v\), its utility, including its enemy diagonal, is
\(v_v^2(x)=2x_a-x_b+2x_c+3(Ay)_v-X.\)
Using the forced masses gives
\(v_v^2(x)=q+3\big((Ay)_v-(R-1)\delta\big).\)
Therefore
\((Ay)_v\geq(R-1)\delta\qquad\text{whenever }y_v>0.\)
Multiply these inequalities by \(y_v\) and sum. Coordinates with \(y_v=0\) contribute zero, so
\(y^{\mathsf T}Ay\geq(R-1)\delta\sum_v y_v=(R-1)\delta X.\)
Normalize by setting \(p=y/X\). Since \(X=R\delta>0\), this is a nonnegative vector summing to one, and
\(p^{\mathsf T}Ap\geq\frac{(R-1)\delta}{X}=1-\frac1R.\)
The lemma now implies
\(1-\frac1R\leq1-\frac1{\omega(H)},\)
which forces \(\omega(H)\geq R\). Thus \(\omega(G)\geq r\).
This proves soundness for arbitrary real masses, including fractional choices.
Conversely, suppose \(H\) contains a clique \(C\) of size \(R\). Choose
\(x_a=x_c=R\delta,\qquad x_b=(R-1)\delta,\)
\(x_v=\delta\quad(v\in C),\)
and set every other mass to zero.
All capacity bounds hold, and \(X=R\delta\).
The auxiliary utilities are
\(v_a^2(x)=2R\delta+2(R-1)\delta-R\delta+2R\delta=q,\)
\(v_b^2(x)=2R\delta+2(R-1)\delta+2R\delta-R\delta=q,\)
\(v_c^2(x)=-R\delta+2(R-1)\delta+2R\delta+2R\delta=q.\)
Each \(v\in C\) has exactly \(R-1\) other clique vertices carrying mass \(\delta\). Thus
\((Ay)_v=(R-1)\delta,\)
and the previously derived vertex-utility formula gives \(v_v^2(x)=q\).
Every type in the actual coalition therefore has utility exactly \(q\). In particular,
\(U_a^k(x)=q\)
for every \(k\geq1\). This proves completeness.
The reduction produces
\(\tau=3n+4\)
listed types. Choosing the smallest qualifying power of two gives \(D=O(n)\), so all mass and threshold encodings have \(O(\log n)\) bits. The friendship relation has \(O(n^2)\) entries, and the construction takes polynomial time.
The friendship weight is the numerical constant \(N=2\). The same construction proves hardness for each fixed \(k\geq1\); it also proves hardness when \(k\) is binary encoded as part of the input.
Together with Section 1, this establishes \(\mathrm{NP}\)-completeness. A deterministic polynomial-time algorithm in the total input length exists only if \(\mathrm P=\mathrm{NP}\). The explicit exact upper bound is \(2^{\tau-1}\operatorname{poly}(\tau,L)\), with no independent alternative-count parameter.
⟨structured verdict parsed — rendered above⟩
The argument establishes the claimed \(\mathrm{NP}\)-completeness in substance, including hardness for constant \(\mathrm N=2\) and every fixed loyalty depth \(\mathrm k\geq1\). I found no false calculation or substantive gap. There is one minor omission: the restriction of the source Clique instances to \(\mathrm{2\leq r\leq n}\) should be explicitly justified.
The support enumeration argument is correct.
For a guessed set \(\mathrm S\) containing the tagged type \(\mathrm a\), the linear program imposes utility constraints for every type in \(\mathrm B_k(S)\). It does not require all guessed types to have positive mass.
For any feasible solution, its actual support \(\mathrm S'\) satisfies \(\mathrm S'\subseteq S\). Every path in the induced graph on \(\mathrm S'\) remains a path in the induced graph on \(\mathrm S\), so
\(\mathrm B_k(S')\subseteq B_k(S)\).
Consequently, every utility constraint required by the actual coalition was imposed by the linear program. This direction correctly handles the discontinuity caused by positive support.
Conversely, choosing the actual support of a feasible coalition gives a feasible linear program. Thus the equivalence is exact.
The invoked linear programming theorem applies: feasibility of a finite system of rational linear inequalities can be decided in time polynomial in its binary encoding length. Here the variables, bounds, zero constraints, and utility inequalities are all rational and explicitly represented. There are \(\mathrm{\tau}\) variables and \(\mathrm{O(\tau)}\) constraints, with total encoding length polynomial in \(\mathrm{\tau,L}\).
A certificate containing only \(\mathrm S\) therefore suffices. No certificate of arbitrary real masses is needed.
The singleton argument for \(\mathrm q\leq0\) is also correct: taking all masses equal to zero gives actual support \(\mathrm{\{a\}}\) and loyal utility zero.
The stated upper bound is valid.
There are \(\mathrm{2^{\tau-1}}\) possible guessed supports containing \(\mathrm a\). Solving the corresponding rational feasibility problems gives the bound
\(\mathrm{2^{\tau-1}\operatorname{poly}(\tau,L)}\).
Breadth-first search computes all relevant finite distances without iterating up to the numerical value of \(\mathrm k\). Finite shortest-path distances are at most \(\mathrm{\tau-1}\), so replacing \(\mathrm k\) by \(\mathrm{\min\{k,\tau-1\}}\) is legitimate. This also handles \(\mathrm{\tau=1}\), when only distance zero is relevant.
The coefficients involving \(\mathrm N\) use its binary encoding length rather than its numerical value as an iteration bound. Both integer encoding lengths are included in \(\mathrm L\). The analysis introduces no independent alternative-count parameter.
The lemma and its proof are correct.
For two nonadjacent positive coordinates, simplicity of the graph gives
\(\mathrm{A_{ii}=A_{jj}=A_{ij}=A_{ji}=0}\).
Hence transferring mass between those coordinates leaves the two corresponding entries of \(\mathrm{Ap}\) unchanged.
The claimed quadratic-form change,
\(\mathrm{2p_j(z_i-z_j)}\),
is correct when all mass at the second coordinate is transferred to the first. The symmetric case is equally valid.
Each transfer preserves nonnegativity and total mass, does not decrease the quadratic form, and strictly decreases the number of positive coordinates. The process therefore terminates with positive support forming a clique.
For a clique support of size \(\mathrm c\), the identity
\(\mathrm{\widehat p^{\mathsf T}A\widehat p=1-\sum_i\widehat p_i^2}\)
correctly uses the absence of diagonal edges. The stated Cauchy–Schwarz inequality gives the bound \(\mathrm{1-1/c}\), and \(\mathrm{c\leq\omega(H)}\) gives the final inequality in the correct direction.
The lemma is applied later to a nonempty simple graph and a nonnegative vector of total mass one, so its hypotheses are satisfied.
The construction satisfies the task’s input requirements.
The prover invokes the standard \(\mathrm{NP}\)-completeness of Clique and identifies its source as [Karp’s original paper](https://link.springer.com/chapter/10.1007/978-1-4684-2001-2_9).
Adding the universal clique of size \(\mathrm{2n}\) gives
\(\mathrm{\omega(H)=\omega(G)+2n}\):
the new vertices can extend any original clique, and the original vertices in any clique of the enlarged graph must themselves form a clique.
The quantities
\(\mathrm{h=3n}\),
\(\mathrm{R=r+2n}\), and
\(\mathrm{3R-2-2h=3r-2>0}\)
are correct.
The masses sum to one because the total mass outside the filler type is
\(\mathrm{(3R+h-1)\delta}\).
Every listed mass is positive and dyadic. The requirement
\(\mathrm{D\geq2(3R+h)}\)
indeed makes the filler mass strictly greater than one half.
The friendship relation is symmetric. Its diagonal choices agree with the utility formulas: the three auxiliary types have friend diagonals, vertex types have enemy diagonals, and the filler is an enemy of every type.
Minor issue — source-instance restriction. Section 3 restricts Clique to \(\mathrm{2\leq r\leq n}\) without explicitly explaining why this restriction preserves \(\mathrm{NP}\)-hardness. This is a routine source-domain clarification rather than a substantive gap.
Minimum requested clarification: explicitly justify the restricted source problem, including how excluded trivial instances are treated, or cite that restricted formulation directly.
The soundness proof correctly covers arbitrary real masses.
First, if the bridge type has zero mass, the tagged utility is bounded above by
\(\mathrm{(2R+2h)\delta}\).
The threshold exceeds this bound by
\(\mathrm{(3r-2)\delta>0}\).
Thus the bridge type must have positive mass. Its friendship with the tag puts it at distance one, making its utility constraint mandatory for every permitted loyalty depth.
The two displayed auxiliary utility formulas correctly account for every friendship and enemy relation. Their weighted sum cancels the vertex mass:
\(\mathrm{v_a^2+2v_b^2=6x_a+6x_b+3x_c-3x_z}\).
The capacity upper bound equals
\(\mathrm{(15R-6)\delta=3q}\).
Since both required utilities are at least the threshold, the lower and upper bounds coincide. Every capacity deficit and the filler mass has a strictly positive coefficient in the upper-bound deficit. Thus the asserted saturated auxiliary masses and zero filler mass follow.
The equality of the two required utilities also follows: their nonnegative excesses over the threshold have weighted sum zero. Substitution then correctly forces total vertex mass
\(\mathrm{X=R\delta>0}\).
For every positive vertex type, friendship with the tag makes its utility mandatory at distance one. The displayed formula
\(\mathrm{v_v^2=2x_a-x_b+2x_c+3(Ay)_v-X}\)
correctly includes the enemy diagonal through the total vertex mass term. Substituting the forced masses yields exactly the claimed threshold comparison.
Multiplying by the nonnegative vertex masses and summing is legitimate. Zero coordinates require no individual utility constraint because they contribute zero to the sum. Normalization by the strictly positive total vertex mass produces a probability vector satisfying
\(\mathrm{p^{\mathsf T}Ap\geq1-1/R}\).
Combining this with the proved lemma forces
\(\mathrm{\omega(H)\geq R}\), hence
\(\mathrm{\omega(G)\geq r}\).
There is no unjustified integrality assumption.
The proposed coalition is feasible.
The selected masses satisfy all capacities, and the total vertex mass is \(\mathrm{R\delta}\).
All three auxiliary utility calculations evaluate to
\(\mathrm{(5R-2)\delta=q}\).
In particular, the calculation for the third auxiliary type correctly treats its relation to the tag as enmity.
Each selected vertex has exactly \(\mathrm{R-1}\) selected neighbors, giving the stated adjacency contribution and utility equal to the threshold.
Every type in the actual support therefore has utility equal to the threshold. This verifies all required utilities for every loyalty depth, including depths that reach the third auxiliary type. Types assigned zero mass introduce no additional support members or constraints.
The construction has \(\mathrm{\tau=3n+4}\) listed types. Since the source range gives \(\mathrm{R=O(n)}\), the smallest qualifying power of two satisfies \(\mathrm{D=O(n)}\). All mass and threshold encodings consequently have \(\mathrm{O(\log n)}\) bits, and the friendship relation has polynomial size.
The reduction uses constant friendship weight \(\mathrm N=2\). Its soundness and completeness hold for every fixed permitted depth; choosing such a depth also establishes hardness of the problem with binary-encoded depth.
Together with membership in \(\mathrm{NP}\), this establishes the claimed classification, subject only to the minor source-domain clarification above. No additional mathematical argument is needed to repair the coalition 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.