Answer: \(\mathrm{NP}\)-complete
Theorem 2 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateThe class of edge sum graph coalition structure generation problems over pla- nar graphs is NP–complete. Moreover, a 3-SAT problem with m clauses can be represented by a GCSG problem over a planar graph with O(m2) nodes.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a planar role graph \(H=(T,F)\), positive rational masses \(\mu_t\) summing to \(1\), rational interaction densities \(a_{tu}\) on edges, and a rational threshold \(K\), decide whether the population mass can be partitioned into coalitions with total value at least \(K\). A coalition \(q\) has mass vector \(x^q\), where \(x_t^q\ge 0\) and \(\sum_q x_t^q=\mu_t\); its total value is \(\sum_q\sum_{\{t,u\}\in F}a_{tu}x_t^q x_u^q\).
A society is given by its support: a list \(T\) of \(\tau\geq 1\) types with positive binary rational masses \(\mu_t\), where \(\sum_{t\in T}\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types.
The input also contains a connected simple undirected planar role graph \(H=(T,F)\), signed binary rational interaction densities \(a_{tu}\) for \(\{t,u\}\in F\), and a binary rational threshold \(K\). Write \(m=|F|\) and let \(L\) be the total input bit length; state running times in \(m,\tau,L\).
A feasible partition is any finite family of nonzero vectors \(x^1,\ldots,x^Q\in\mathbb{R}_{\geq 0}^{T}\), with \(Q\) unrestricted, such that \(\sum_{q=1}^{Q}x_t^q=\mu_t\) for every type. Each coalition's positive support \(\{t:x_t^q>0\}\) must induce a connected subgraph of \(H\); singleton supports are allowed.
Its total value is \(V=\sum_{q=1}^{Q}\sum_{\{t,u\}\in F}a_{tu}x_t^qx_u^q\). There are no within-type interactions or additional terms. The decision problem asks whether a feasible partition has \(V\geq K\).
Is this continuous decision problem solvable in polynomial time in \(m,\tau,L\), or is it NP-hard?
The discrete decision problem, partitioning planar graph vertices into connected coalitions and summing weights of edges internal to coalitions, is NP-complete ([Voice, Polukarov and Jennings](https://doi.org/10.1613/jair.3715)). No complexity result for this exact continuous mass model was located in the literature search.
The continuous decision problem is \(\mathrm{NP}\)-complete.
The key fact is that splitting a type’s mass cannot improve the optimum: every feasible continuous partition is dominated by a feasible partition in which each type places its entire mass in one coalition. This holds for arbitrary signed interaction densities.
Call a feasible partition unsplit if, for each type \(t\), exactly one coalition contains its entire mass \(\mu_t\).
Lemma. Every feasible continuous partition has an unsplit feasible partition of at least the same value.
Proof. Fix any feasible family \(x^1,\ldots,x^Q\). Since \(\mu_t>0\), define
\(p_t^q=x_t^q/\mu_t\).
For each \(t\), these numbers are nonnegative and satisfy \(\sum_{q=1}^Q p_t^q=1\). Independently for each type, choose a random label \(Z_t\) with \(\Pr(Z_t=q)=p_t^q\). Assign the entire mass \(\mu_t\) to that label.
Temporarily disregard connectedness. The resulting value is
\(W(Z)=\sum_{\{t,u\}\in F}a_{tu}\mu_t\mu_u\,\mathbf{1}_{\{Z_t=Z_u\}}\).
Every edge has distinct endpoints because the graph is simple. Independence therefore gives
\(\Pr(Z_t=Z_u)=\sum_{q=1}^Q p_t^q p_u^q\).
Consequently,
\(\mathbb{E}[W(Z)] =\sum_{\{t,u\}\in F}a_{tu}\mu_t\mu_u\sum_{q=1}^Q p_t^q p_u^q =\sum_{q=1}^Q\sum_{\{t,u\}\in F}a_{tu}x_t^q x_u^q =V.\)
This is an equality, so negative densities cause no difficulty. The random experiment has finitely many outcomes; hence some outcome satisfies \(W(Z)\geq V\).
Fix such an outcome. For each nonempty label class \(S_q=\{t:Z_t=q\}\), split \(S_q\) into the connected components of \(H[S_q]\). Give every resulting component its own coalition, containing the full masses of its types.
This operation preserves the value. Indeed, if the endpoints of an edge had the same label, that edge itself connects them within the corresponding induced subgraph, so they remain in the same component. Endpoints with different labels remain separated. Thus every edge’s contribution is unchanged.
The resulting partition is feasible and unsplit, and has at most \(\tau\) coalitions. Its value is at least \(V\). \(\square\)
Define the effective edge weights
\(b_{tu}=a_{tu}\mu_t\mu_u.\)
For a partition \(\mathcal{P}\) of \(T\) into nonempty connected blocks, define
\(D(\mathcal{P}) =\sum_{C\in\mathcal{P}}\sum_{\{t,u\}\in F:\,t,u\in C}b_{tu}.\)
Every such partition gives a feasible continuous partition: for each block \(C\), use the vector whose coordinate at \(t\) is \(\mu_t\) when \(t\in C\), and zero otherwise. Its continuous value is exactly \(D(\mathcal{P})\).
Conversely, the lemma shows that every feasible continuous value is bounded above by the value of some such discrete partition. Therefore
\(\max_{\text{feasible continuous partitions}}V =\max_{\text{connected vertex partitions }\mathcal{P}}D(\mathcal{P}).\)
The maximum on the right exists because there are finitely many vertex partitions. Thus the continuous maximum is attained, despite unrestricted \(Q\) and real-valued coalition masses.
In particular,
\(\exists\text{ feasible continuous partition with }V\geq K \quad\Longleftrightarrow\quad \exists\text{ connected vertex partition }\mathcal{P}\text{ with }D(\mathcal{P})\geq K.\)
The discrete source problem has a connected simple planar graph \(G=(N,E)\), signed rational edge weights \(w_{tu}\), and threshold \(B\). It asks whether a connected vertex partition has internal-edge weight at least \(B\). This is the edge-sum problem proved \(\mathrm{NP}\)-complete by Voice, Polukarov and Jennings, Theorem 2; their graph model is connected and simple. [Source](https://jair.org/index.php/jair/article/download/10781/25742/20089).
Write \(n=|N|\) and \(e=|E|\). The following construction uses dyadic masses, so it also works if “binary rational” requires terminating binary expansions.
Let \(p\) be the smallest power of two satisfying \(p\geq n\). Add \(p-n\) new pendant vertices to an arbitrary original vertex, giving every new edge weight zero. Call the resulting graph \(H=(T,F)\), and write \(\widehat w\) for its edge weights.
The graph remains connected, simple, and planar. Moreover, padding preserves the discrete optimum:
Now construct the continuous instance by setting
\(\mu_t=1/p\quad(t\in T),\qquad a_{tu}=p^2\widehat w_{tu}\quad(\{t,u\}\in F),\qquad K=B.\)
All masses are positive dyadic rationals, and their sum is one. Its effective edge weights are
\(a_{tu}\mu_t\mu_u =p^2\widehat w_{tu}\cdot p^{-1}\cdot p^{-1} =\widehat w_{tu}.\)
By Section 2, this continuous instance is a yes-instance exactly when the padded discrete instance is, and therefore exactly when the original discrete instance is.
For the output parameters,
\(\tau=p<2n,\qquad m=e+p-n.\)
If the source encoding length is \(L_{\mathrm d}\), the output satisfies
\(L=O\!\left(L_{\mathrm d}+(e+n)\log(n+1)\right).\)
Multiplying weights by \(p^2\) adds only \(O(\log(n+1))\) bits per weight. Hence the construction runs in polynomial time and proves \(\mathrm{NP}\)-hardness.
A certificate assigns each type a coalition label in \(\{1,\ldots,\tau\}\), using \(O(\tau\log(\tau+1))\) bits. The verifier checks that each nonempty label class induces a connected subgraph and computes its exact value using \(b_{tu}=a_{tu}\mu_t\mu_u\).
Here is an explicit polynomial bit bound. Write the input rationals as
\(\mu_t=r_t/s_t,\qquad a_{tu}=c_{tu}/d_{tu},\qquad K=k/d_K,\)
with positive denominators. Choose the common denominator
\(D=d_K\left(\prod_{\{t,u\}\in F}d_{tu}\right)\left(\prod_{t\in T}s_t^2\right).\)
Its bit length is \(O(L)\). For every edge,
\(B_{tu}=c_{tu}r_tr_u\,\frac{D}{d_{tu}s_ts_u}\)
is an integer equal to \(Db_{tu}\). Compare the sum of \(B_{tu}\) over internal edges with \(kD/d_K\). All these integers and sums have \(O(L)\) bits. Using ordinary integer arithmetic, certificate verification takes
\(O((m+\tau)L^2)\)
bit operations. The rounding lemma guarantees such a certificate for every continuous yes-instance, proving membership in \(\mathrm{NP}\).
For completeness, an exact exhaustive algorithm runs in
\(O(2^m(m+\tau)L^2)\)
bit operations: enumerate all edge subsets, take their connected-component partitions, and evaluate each partition. This covers every connected vertex partition because choosing a spanning tree inside each block realizes that partition as the components of an edge subset.
Thus the requested problem is \(\mathrm{NP}\)-complete, and a polynomial-time algorithm in \(m,\tau,L\) would imply \(\mathrm{P}=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The prover resolves the assigned problem correctly: the continuous decision problem is \(\mathrm{NP}\)-complete. No major or minor mathematical issues were found.
The probabilities \(p_t^q=x_t^q/\mu_t\) are well-defined because every mass is positive. Feasibility gives nonnegativity and \(\sum_q p_t^q=1\), so each random label distribution exists.
Every edge has distinct endpoints. Thus independence applies to its endpoint labels, giving
\[
\Pr(Z_t=Z_u)=\sum_q p_t^q p_u^q.
\]
Substitution into the expected objective yields exactly the original continuous value. All sums are finite, so exchanging their order requires no additional justification.
This is an equality for arbitrary signed densities; no inequality involving negative coefficients is used. Since the random experiment has finitely many outcomes, some outcome of positive probability has value at least its expectation. The argument needs neither rational coalition coordinates nor an efficient implementation of this rounding.
For each label class, the prover takes connected components of its induced subgraph. These components are nonempty connected supports.
The assertion that this operation preserves value is justified edge by edge. If an edge’s endpoints have the same label, that edge belongs to the induced subgraph and places both endpoints in the same connected component. If their labels differ, they remain separated. Hence the indicator determining every edge contribution is unchanged, regardless of its sign.
Every type subsequently receives its entire mass in exactly one coalition. Mass conservation holds, every coalition vector is nonzero, and the number of coalitions is at most \(\tau\). The lemma therefore establishes precisely its stated conclusion.
The effective weights \(b_{tu}=a_{tu}\mu_t\mu_u\) exactly represent the value of unsplit coalitions. The construction from a connected vertex partition produces a feasible continuous partition with identical value.
In the other direction, the rounding lemma dominates every feasible continuous partition by a connected vertex partition. Since the set of vertex partitions is finite and nonempty, its maximum exists. Its continuous realization then attains a value bounding all feasible continuous values.
Consequently, both the equality of maxima and the threshold equivalence follow. There is no missing compactness assumption despite unrestricted finite \(Q\).
The citation identifies the required edge-sum planar hardness theorem. The paper defines simple undirected graphs in Section 2.1, assumes connected graphs in its model, and states planar edge-sum \(\mathrm{NP}\)-completeness in Theorem 2. Its hardness construction uses integer edge weights, so it supplies instances within the signed binary rational source class. See the [paper, Sections 2 and 5.1](https://arxiv.org/pdf/1401.6428).
Thus the reduction does not rely on hardness for a broader graph class or on an incompatible valuation function. No additional source-problem lemma is needed.
Attaching distinct new pendant vertices preserves simplicity, connectedness, and planarity. Extending original partitions with singleton new vertices preserves value.
Conversely, removing the added vertices and splitting remaining blocks into connected components preserves every original internal-edge contribution: an original edge whose endpoints remain in a block connects them within that remaining induced subgraph. Original edges previously crossing blocks remain crossing. Deleted edges have weight zero, so they do not affect value. This proves the claimed preservation of the discrete optimum.
The padded graph has exactly \(p\) vertices. Accordingly, \(\mu_t=1/p\) gives positive dyadic masses summing to one, and the density scaling yields
\[
a_{tu}\mu_t\mu_u=\widehat w_{tu}.
\]
The threshold is unchanged, so the reduction preserves yes- and no-instances.
The parameter identities and bounds are correct: \(\tau=p<2n\) for every \(n\geq1\), and \(m=e+p-n\). The stated encoding bound accounts for added vertices, edges, mass encodings, and the weight scaling. Polynomial construction time follows.
Coalition labels require \(O(\tau\log(\tau+1))\) bits. Checking connectivity within each nonempty label class verifies precisely the support constraint.
The common denominator has \(O(L)\) bits. Because edge endpoints are distinct, each denominator \(d_{tu}s_ts_u\) divides the displayed product \(D\), including when endpoint denominators share factors. Thus every displayed \(B_{tu}\) is an integer equal to \(Db_{tu}\).
Each scaled edge value and the scaled threshold have \(O(L)\) bits. Summing at most \(m\) such values adds only \(O(\log(m+1))\) bits, which is absorbed by \(O(L)\). Building the denominator and performing the required products, exact divisions, additions, and comparison with ordinary integer arithmetic fits the claimed \(O((m+\tau)L^2)\) bit bound.
Certificate soundness follows from the continuous realization of an accepted connected vertex partition. Completeness follows from the rounding lemma, even when the original continuous witness has real coordinates.
Finally, enumeration of edge subsets covers every connected vertex partition by the spanning-tree argument explicitly given in the output. The bound \(O(2^m(m+\tau)L^2)\) is valid. For \(\tau=1\) and \(m=0\), the unique vertex partition is included and its value is zero, so the degenerate allowed case creates no exception.
No repair or additional clarification is required. The output establishes hardness and membership in \(\mathrm{NP}\), rather than merely transferring an optimization heuristic or establishing a relaxation bound.
⟨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.