Answer: \(\mathrm{NP}\text{-hard}\), even with two primary vertices, no backbone vertices, equal masses, and a guaranteed finite optimum.
Theorem 1 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateCG-BANZHAF is #P-hard, even if there are no backbone vertices, i.e., Vb = ∅.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite role-network template \(H\), fixed primary and backbone vertices, positive integer role weights \(w_t\) for \(t\in T\), and a target role \(r\), let \(W_H(K)\) indicate whether the primary vertices are connected when exactly the standard roles in \(K\) are available. With \(W=\sum_{t\in T}w_t\) and \(\mu_t=w_t/W\), compute the exact value and a maximizing set for \(\rho_r=1-\max_{K\subseteq T\setminus\{r\}: W_H(K\cup\{r\})=1,\,W_H(K)=0}\sum_{t\in K}\mu_t\), or return \(+\infty\) if no such \(K\) exists. This is the decay rate \(-\lim_{q\to\infty}(qW)^{-1}\log_2\beta_i(G_q)\) for a representative server \(i\) of role \(r\) in the \(q\)-fold replicated template, with independent fair failures.
Let \(H=(V,E)\) be a finite simple undirected graph with a partition \(V=P\mathbin{\dot\cup}B\mathbin{\dot\cup}T\) into primary vertices, backbone vertices, and standard roles, with \(|P|\geq2\), and a target \(r\in T\). Primary and backbone vertices are always available, including as internal vertices of paths. Define \(W_H(K)=1\) precisely when all primary vertices lie in one connected component of \(H[P\cup B\cup K]\), for \(K\subseteq T\).
A society is given by its support: the list of the \(\tau=|T|\) 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 also supplies positive binary-encoded integers \(w_t\), with \(W=\sum_{t\in T}w_t\), \(\mu_t=w_t/W\), and \(\sum_{t\in T}\mu_t=1\). Set \(m=|V|\) and let \(L\) be the total input bit length.
Define \(\mathcal F_r=\{K\subseteq T\setminus\{r\}:W_H(K\cup\{r\})=1,\ W_H(K)=0\}\). Compute exactly \(\rho_r=1-\max_{K\in\mathcal F_r}\sum_{t\in K}\mu_t\) and a maximizing set; return \(+\infty\) if \(\mathcal F_r=\varnothing\). Any maximizing set is acceptable.
Is this exact value-and-maximizer problem solvable in polynomial time in \(m,\tau,L\), or is it NP-hard?
For finite vertex connectivity games, exact Banzhaf-index computation is \(\#\mathrm P\)-hard even with no backbone vertices; the corresponding critical-coalition counting problem is \(\#\mathrm P\)-complete. [Source](https://aamas.csc.liv.ac.uk/Proceedings/aamas08/proceedings/pdf/paper/AAMAS08_0046.pdf)
A search located no result settling the exact mass-weighted problem defined here.
The exact value-and-maximizer problem is \(\mathrm{NP}\)-hard. This holds even when:
We prove this by a polynomial reduction from a known \(\mathrm{NP}\)-complete induced-cycle problem.
An induced path is a path whose vertices induce exactly its path edges.
Lemma. Suppose \(P=\{s,t\}\), \(B=\varnothing\), and \(r\in T\). Then \(\mathcal F_r\neq\varnothing\) if and only if \(H\) contains an induced path with endpoints \(s,t\) that contains \(r\).
Proof. Let \(K\in\mathcal F_r\). The graph \(H[\{s,t,r\}\cup K]\) contains an \(s\)-\(t\) path. Every such path contains \(r\), because \(s,t\) are disconnected in \(H[\{s,t\}\cup K]\).
Choose a shortest \(s\)-\(t\) path in \(H[\{s,t,r\}\cup K]\). It is induced: an edge between nonconsecutive path vertices would give a shorter path. Since the ambient graph is an induced subgraph of \(H\), the path is also induced in \(H\). It contains \(r\).
Conversely, let \(Q\) be an induced \(s\)-\(t\) path containing \(r\), and set \(K=V(Q)\setminus\{s,t,r\}\). Including \(r\) makes the primaries connected. Removing the internal vertex \(r\) from the induced path disconnects its endpoints. Thus \(K\in\mathcal F_r\). \(\square\)
We use the following established theorem:
Induced-cycle theorem. Given a finite simple graph \(G\) and two designated edges \(e,f\), deciding whether an induced cycle contains both edges is \(\mathrm{NP}\)-complete.
This is stated as Theorem 1.1 in Chudnovsky and Seymour’s [*The three-in-a-tree problem*](https://www.columbia.edu/~mc2775/threeinatree.pdf), attributed there to Bienstock.
We may restrict to distinct edges. Indeed, if \(e=f=st\), the answer is yes exactly when \(s,t\) are connected in \(G-e\): a shortest \(s\)-\(t\) path in \(G-e\), together with \(e\), is an induced cycle. This case is polynomially decidable and can be replaced by a fixed distinct-edge yes-instance or no-instance.
Consider therefore an instance with distinct edges \(e=st\) and \(f=uv\). Construct \(H_0\) by deleting \(e\) and subdividing \(f\) with a fresh vertex \(r\):
\(V(H_0)=V(G)\cup\{r\},\qquad E(H_0)=(E(G)\setminus\{e,f\})\cup\{ur,rv\}.\)
Here and below, \(xy\) denotes the undirected edge \(\{x,y\}\). Set \(P=\{s,t\}\), \(B=\varnothing\), and \(T_0=V(H_0)\setminus\{s,t\}\).
Claim. An induced cycle of \(G\) contains \(e,f\) if and only if an induced \(s\)-\(t\) path of \(H_0\) contains \(r\).
Proof. Given such a cycle, deleting \(e\) and subdividing \(f\) produces the required induced path.
Conversely, \(r\) has precisely the neighbors \(u,v\). Since \(r\) is internal on the required path, the path contains the consecutive segment \(u,r,v\), in one orientation. Replace that segment by \(uv\), and restore \(st\). This gives a cycle containing \(e,f\).
It is induced: among its vertices, the only edges of \(G\) absent from \(H_0\) are \(e,f\), and both become cycle edges. All other possible chords are excluded by the inducedness of the path. Finally, the path cannot consist only of \(s,r,t\), since that would imply \(f=e\). Consequently the resulting cycle has at least three vertices. \(\square\)
By the lemma, the source instance is positive exactly when \(H_0\) has a critical coalition. The next construction converts this existence question into an optimization threshold while guaranteeing a finite optimum.
Write \(n=|T_0|\) and set \(q=n+2\). Let \(N\) be the smallest power of two satisfying \(N\ge 3q\), and put \(d=N-3q\).
Add the following fresh standard-role vertices:
Retain all edges of \(H_0\), and add exactly
\(\{sa,ar,rb,bt\}\cup\{ax_i,x_it,by_i,y_is:1\le i\le q\}.\)
Call the resulting graph \(H\). Keep \(P=\{s,t\}\), \(B=\varnothing\), and target \(r\). Its standard-role set is
\(T=T_0\mathbin{\dot\cup}\{a,b\}\mathbin{\dot\cup}A\mathbin{\dot\cup}C\mathbin{\dot\cup}D.\)
Assign \(w_z=1\) to every \(z\in T\). Then
\(\tau=n+2+2q+d=3q+d=N,\qquad W=N,\qquad \mu_z=1/N.\)
Since \(N\) is a power of two, every mass has a terminating binary expansion.
Guaranteed feasibility. The coalition \(K=\{a,b\}\) is critical. Without \(r\), the induced graph on \(\{s,t,a,b\}\) has exactly the edges \(sa,bt\), because \(st\notin E(H_0)\). Thus the primaries are disconnected. Including \(r\) supplies the path \(s,a,r,b,t\), so they become connected.
In particular, \(\mathcal F_r\neq\varnothing\) for every constructed instance.
Equal masses give
\(\rho_r=1-\dfrac{1}{N}\max_{K\in\mathcal F_r}|K|.\)
We prove the equivalence
\(\text{the source instance is positive}\quad\Longleftrightarrow\quad \rho_r\le \dfrac qN.\)
Equivalently, the right-hand condition asks whether some critical coalition has size at least \(N-q=2q+d\).
Suppose the source instance is positive. Section 2 and the lemma give a critical coalition \(K_0\subseteq T_0\setminus\{r\}\) in \(H_0\).
Take
\(K=K_0\cup A\cup C\cup D.\)
The vertices \(a,b\) are absent. Consequently, every included \(x_i\) is a leaf attached to \(t\), every included \(y_i\) is a leaf attached to \(s\), and every vertex of \(D\) is isolated.
These added vertices cannot change connectivity between \(s,t\): none can be an internal vertex of a simple \(s\)-\(t\) path. This remains true both with and without \(r\). Hence \(K\) is critical in \(H\), and
\(|K|=|K_0|+2q+d\ge N-q.\)
Therefore \(\rho_r\le q/N\).
Suppose \(K\in\mathcal F_r\) satisfies \(|K|\ge 2q+d\).
First, \(K\) must meet both \(A\) and \(C\). If it misses either one, its size is at most
\((n-1)+2+q+d=2q+d-1.\)
Here \(n-1\) counts the available original standard roles other than \(r\), the next \(2\) counts \(a,b\), and \(q\) counts the remaining added group. This contradicts the assumed size.
Choose \(x_i\in K\cap A\) and \(y_j\in K\cap C\). The vertex \(a\) cannot belong to \(K\), since otherwise \(s,a,x_i,t\) is a path connecting the primaries without \(r\). Similarly, \(b\notin K\), because \(s,y_j,b,t\) would connect the primaries without \(r\).
Set \(K_0=K\cap(T_0\setminus\{r\})\). With \(a,b\) absent, all retained vertices outside \(H_0\) are leaves attached to one primary or isolated vertices. As in the forward implication, they cannot affect connectivity between the primaries, either with or without \(r\).
Thus criticality of \(K\) implies criticality of \(K_0\) in \(H_0\). The lemma and Section 2 now imply that the source instance is positive. This proves the equivalence.
The construction has polynomial size. Indeed, \(q=n+2\) and \(3q\le N<6q\), so it adds only linearly many vertices and edges. Each support type is explicitly listed, every integer weight is \(1\), and each mass \(1/N\) has an encoding of length \(O(\log N)\). The comparison threshold \(q/N\) also has polynomial encoding length.
Therefore an algorithm computing the exact value and a maximizer in polynomial time in \(m,\tau,L\) would decide the source \(\mathrm{NP}\)-complete problem by comparing its returned value with \(q/N\). This proves \(\mathrm{NP}\)-hardness, including under all the restrictions stated above.
For completeness, the associated threshold decision problem belongs to \(\mathrm{NP}\). A certificate is a coalition \(K\). Two graph searches verify its criticality, and binary integer arithmetic verifies
\(1-\dfrac{\sum_{z\in K}w_z}{W}\le c\)
for the supplied rational threshold \(c\). All these computations take polynomial time in the input length. Hence the threshold decision problem is \(\mathrm{NP}\)-complete.
The requested exact value-and-maximizer problem is therefore \(\mathrm{NP}\)-hard and cannot have a polynomial-time algorithm unless \(\mathrm P=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The proof is correct and resolves the task. It establishes \(\mathrm{NP}\)-hardness of the exact value-and-maximizer problem under all five stated restrictions. No major or minor mathematical issues were found.
The lemma is correct in both directions.
There is no assumption that other standard roles are available: both directions use exactly the induced subgraphs required by the task.
The cited theorem is accurately stated. Theorem 1.1 of [Chudnovsky and Seymour’s paper](https://www.columbia.edu/~mc2775/threeinatree.pdf) asserts \(\mathrm{NP}\)-completeness for an induced cycle containing two designated edges in a finite simple graph. Its definition of cycle permits triangles, consistent with the proof.
The restriction to distinct edges is justified. When \(e=f=st\), connectivity in \(G-e\) is necessary and sufficient. A shortest connecting path has no chords in \(G-e\); restoring \(st\) supplies the closing cycle edge. Thus this exceptional case can be decided in polynomial time and mapped to a fixed distinct-edge instance of the corresponding answer.
The construction of \(H_0\) preserves the claimed equivalence:
This also covers distinct designated edges sharing an endpoint; disjointness is not needed.
The vertex counts and mass assignments are correct. With \(q=n+2\),
\[ \tau=n+2+2q+d=3q+d=N. \]
The smallest power of two at least \(3q\) satisfies
\[ 3q\le N<6q, \]
so \(d\ge0\) and the padding has linear size.
All standard roles receive positive integer weight \(1\), giving \(W=N\) and mass \(1/N\). These masses sum to \(1\) and have terminating binary expansions because \(N\) is a power of two. The explicit support representation has polynomial length.
Guaranteed feasibility is also correct. On the vertices \(\{s,t,a,b\}\), the only edges are \(sa,bt\): the original edge \(st\) was deleted, and \(a,b\) are fresh. Adding \(r\) supplies the path \(s,a,r,b,t\). Thus \(\{a,b\}\) is critical regardless of the source answer.
Equal masses justify
\[ \rho_r=1-\frac{\max_{K\in\mathcal F_r}|K|}{N}. \]
Since \(N=3q+d\), the threshold \(\rho_r\le q/N\) is exactly the existence of a critical coalition of size at least \(2q+d\).
Forward direction. The coalition \(K_0\cup A\cup C\cup D\) excludes \(a,b\). Consequently the added vertices are leaves attached to a single primary or isolated vertices, both before and after adding \(r\). They cannot change connectivity between the primaries. Criticality is preserved, and the coalition has the required size.
Reverse direction. The counting bound is correct. If either \(A\) or \(C\) is missed, then
\[ |K|\le(n-1)+2+q+d=2q+d-1, \]
contradicting the threshold. The term \(n-1\) correctly excludes the target \(r\).
Once \(K\) meets both groups, including \(a\) would create the path \(s,a,x_i,t\) without \(r\), and including \(b\) would create \(s,y_j,b,t\). Thus criticality forces both vertices to be absent.
The remaining added vertices cannot affect primary connectivity. Therefore restricting \(K\) to the original standard roles preserves criticality in \(H_0\). The preceding equivalences then recover a positive source instance.
The construction, weights, masses, and threshold all have polynomial encoding length. An exact value algorithm would decide the source problem by the stated rational comparison. The requested maximizer does not weaken this implication: an algorithm returning both outputs necessarily returns the value.
The threshold problem belongs to \(\mathrm{NP}\): a coalition is a polynomial-size certificate, graph searches verify its criticality, and exact integer arithmetic verifies the rational inequality in polynomial time. Empty critical families simply supply no accepting certificate. Combined with the reduction, this establishes threshold \(\mathrm{NP}\)-completeness.
The conclusion about the exact optimization problem follows. The supplied counting-hardness result is not needed for this argument.
No additional lemma, correction, or clarification is required.
⟨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.