Answer: \(\mathrm{NP}\)-hard under polynomial-time Turing reductions; the decision part is \(\mathrm{coNP}\)-complete.
Theorem 4 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateECM is coNP-complete in general CGs, even if the imputation to be tested is the equal imputation p = ( 1 n, . . . , 1 n) and if there is a single backbone vertex.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite graph \(G=(V,E)\) with primary vertices \(V_p\), backbone vertices \(V_b\), and standard server-role types \(T=V_s\), rational masses \(\mu_t\ge0\) with \(\sum_t\mu_t=1\), thresholds \(0<\theta_t\le\mu_t\), nonnegative reward densities \(q_t\) with \(\sum_t\mu_tq_t=1\), and rational \(\epsilon\), let \(x_t\in[0,\mu_t]\) be participating mass and declare role \(t\) active iff \(x_t\ge\theta_t\). Decide whether every \(x\) for which \(V_p\) is connected in \(G[V_p\cup V_b\cup\{t\in T:x_t\ge\theta_t\}]\) satisfies \(\sum_tq_tx_t\ge1-\epsilon\); equivalently, decide whether \(\min\{\sum_tq_tx_t:x\in[0,\mu],\ v_\theta(x)=1\}\ge1-\epsilon\), and return a violating \(x\) when not.
Let \(G=(V,E)\) be a finite simple undirected graph with a partition \(V=V_p\sqcup V_b\sqcup T\) into primary vertices, backbone vertices, and standard server roles; put \(m=|V|\). Assume \(|V_p|\ge2\) and that all primary vertices lie in one connected component of \(G\).
A society is given by its support: the list of the \(\tau=|T|\) types with positive mass, each mass a binary rational; \(\tau\) is the support size, not the number of possible types. Each type corresponds to one standard vertex. Require \(\sum_{t\in T}\mu_t=1\).
Input also includes binary rational thresholds \(0<\theta_t\le\mu_t\), reward densities \(q_t\ge0\) with \(\sum_t\mu_tq_t=1\), and \(\epsilon\in\mathbb Q\). Let \(L\) be the total input bit length.
A coalition is any real vector \(x\in\prod_t[0,\mu_t]\). Role \(t\) is available exactly when \(x_t\ge\theta_t\); primary and backbone vertices are always available, including as intermediate vertices on paths.
Define \(v_\theta(x)=1\) exactly when all primary vertices lie in one connected component of \(G[V_p\cup V_b\cup\{t:x_t\ge\theta_t\}]\), and otherwise set \(v_\theta(x)=0\). Its allocated reward is \(p(x)=\sum_tq_tx_t\).
Decide whether every winning coalition satisfies \(p(x)\ge1-\epsilon\); on a negative answer, return a rational winning coalition with \(p(x)<1-\epsilon\).
Is this decision-and-witness problem solvable in time polynomial in \(m,\tau,L\), or is it NP-hard under polynomial-time Turing reductions?
Discrete \(\epsilon\)-core membership is coNP-complete even with equal rewards and a single backbone vertex; it is polynomial-time solvable on trees. [Source](https://arxiv.org/pdf/1402.0572)
No result settling this exact thresholded mass problem was located in the literature search.
The decision-and-witness problem is \(\mathrm{NP}\)-hard under polynomial-time Turing reductions. More precisely, its decision part is \(\mathrm{coNP}\)-complete under polynomial-time many-one reductions.
Hardness holds even with a single backbone vertex, equal masses, reward densities \(q_t=1\), and strictly interior thresholds \(\theta_t=\mu_t/2\). Thus the result does not depend on taking the discrete boundary case \(\theta_t=\mu_t\).
Call \(S\subseteq T\) winning if all primary vertices belong to one connected component of \(G[V_p\cup V_b\cup S]\). Define its cost by
\[ c(S)=\sum_{t\in S}q_t\theta_t. \]
For each subset \(S\), define the rational coalition \(x^S\) by \(x^S_t=\theta_t\) when \(t\in S\), and \(x^S_t=0\) otherwise.
Because \(0<\theta_t\le\mu_t\), this coalition is feasible and its available roles are exactly \(S\). Consequently, \(x^S\) is winning exactly when \(S\) is winning, and \(p(x^S)=c(S)\).
Conversely, take any real coalition \(x\), and put \(S(x)=\{t\in T:x_t\ge\theta_t\}\). The coalitions \(x\) and \(x^{S(x)}\) have exactly the same available vertices. Moreover, nonnegativity of every \(q_t\) gives
\[ p(x)=\sum_{t\in T}q_tx_t \ge\sum_{t\in S(x)}q_t\theta_t =c(S(x)). \]
Therefore,
\[ \exists x\text{ winning with }p(x)<1-\epsilon \quad\Longleftrightarrow\quad \exists S\subseteq T\text{ winning with }c(S)<1-\epsilon. \]
In particular, every negative instance has a rational witness whose coordinates are copied from the input thresholds or are zero.
A subset \(S\) is a polynomial-size certificate: connectivity can be checked by graph traversal, and its cost can be compared with \(1-\epsilon\) using exact rational arithmetic. Products and sums of the input rationals have polynomial bit length. Hence the complement of the decision problem belongs to \(\mathrm{NP}\), and the decision problem belongs to \(\mathrm{coNP}\).
We use the standard \(\mathrm{NP}\)-completeness of Vertex Cover, also used in the discrete connectivity-game hardness proof in [Bachrach, Porat, and Rosenschein, Theorem 4](https://arxiv.org/pdf/1402.0572). The following construction handles the thresholded masses and the strict inequality explicitly.
Let \(H=(U,F)\) be a finite simple graph, with \(n=|U|\), and let \(k\) be the requested cover size. We may restrict to \(n\ge2\), \(F\ne\varnothing\), and \(0\le k<n\). Excluded instances have immediately decidable answers and can be replaced by fixed yes or no instances satisfying these restrictions, so the restricted problem remains \(\mathrm{NP}\)-complete.
Let \(N\) be the smallest power of two satisfying \(N\ge n\). Then \(n\le N<2n\).
Construct the target graph as follows:
Thus \(\tau=N\), \(|V_p|=|F|+1\ge2\), and \(m=N+|F|+2\). The entire graph is connected: every standard vertex and \(a\) is adjacent to \(b\), and every \(p_e\) has a path to \(b\) through an endpoint’s standard vertex.
For every standard role \(t\), set
\[ \mu_t=\frac1N,\qquad \theta_t=\frac1{2N},\qquad q_t=1. \]
These values satisfy all requirements:
\[ \sum_{t\in T}\mu_t=1,\qquad \sum_{t\in T}\mu_tq_t=1,\qquad 0<\theta_t=\frac{\mu_t}{2}<\mu_t. \]
Set
\[ \epsilon=1-\frac{2k+1}{4N}. \]
All these numbers are dyadic rationals with encoding length \(O(\log n)\). Because \(N<2n\), both the explicit support and the entire constructed instance have polynomial size.
For \(S\subseteq T\), define the corresponding original vertices by \(C(S)=\{u\in U:t_u\in S\}\).
Claim. The subset \(S\) is winning exactly when \(C(S)\) is a vertex cover of \(H\).
Proof. Suppose \(S\) is winning. For an edge \(e=\{u,v\}\), if neither \(t_u\) nor \(t_v\) belongs to \(S\), then \(p_e\) is isolated in the available induced graph. It cannot be connected to the distinct primary vertex \(a\), contradicting winning. Hence at least one endpoint of every edge belongs to \(C(S)\).
Conversely, suppose \(C(S)\) covers every edge. Each primary vertex \(p_e\) then has an available path \(p_e,t_u,b\) through a selected endpoint \(u\). The primary vertex \(a\) is directly adjacent to \(b\). Thus all primary vertices belong to the component containing \(b\), so \(S\) is winning. \(\square\)
The additional standard vertices have no incident edges to any \(p_e\), so they cannot help cover an original edge.
Every subset has cost \(c(S)=|S|/(2N)\). Therefore,
\[ c(S)<1-\epsilon \quad\Longleftrightarrow\quad \frac{|S|}{2N}<\frac{2k+1}{4N} \quad\Longleftrightarrow\quad 2|S|<2k+1 \quad\Longleftrightarrow\quad |S|\le k, \]
where the last equivalence uses that \(|S|\) and \(k\) are integers.
If \(H\) has a vertex cover \(C\) of size at most \(k\), select precisely the roles \(t_u\) with \(u\in C\). The resulting canonical coalition is winning and satisfies \(p(x^S)<1-\epsilon\).
Conversely, if any real winning coalition violates the reward inequality, Section 1 yields a winning subset \(S\) with \(|S|\le k\). By the claim, \(C(S)\) is a vertex cover, and \(|C(S)|\le|S|\le k\).
We have proved
\[ (H,k)\text{ is a yes-instance of Vertex Cover} \quad\Longleftrightarrow\quad \text{the constructed instance has answer no}. \]
The reduction proves that the complement of the decision problem is \(\mathrm{NP}\)-hard. Together with Section 1, it is \(\mathrm{NP}\)-complete; equivalently, the decision problem is \(\mathrm{coNP}\)-complete.
A single call to an oracle for the requested decision-and-witness problem decides Vertex Cover: construct the instance and reverse its decision answer. This establishes \(\mathrm{NP}\)-hardness under polynomial-time Turing reductions.
The real-valued domain creates no witness-size obstruction. Every violating coalition can be replaced by one with \(x_t\in\{0,\theta_t\}\), of polynomial encoding length. Thus the hardness is already present in choosing which roles to activate. A polynomial-time algorithm for the full problem would imply \(\mathrm{P}=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The prover resolves the task correctly. The decision problem is coNP-complete under polynomial-time many-one reductions, and the requested decision-and-witness problem is NP-hard under polynomial-time Turing reductions. No major or minor mathematical issues were found.
The canonical coalition \(x^S\) is feasible because every selected coordinate satisfies \(0<\theta_t\le\mu_t\). Its available roles are exactly \(S\): selected roles meet their thresholds, while unselected roles have coordinate zero, strictly below their positive thresholds.
Thus its winning status agrees exactly with that of \(S\), and its reward is \(c(S)\).
For any feasible real coalition \(x\), the subset \(S(x)\) preserves precisely the available vertices. The inequality
\(p(x)\ge c(S(x))\)
is valid: selected coordinates satisfy \(x_t\ge\theta_t\), and all omitted contributions are nonnegative because \(q_t\ge0\) and \(x_t\ge0\).
Both directions of the asserted existential equivalence therefore hold, including the strict reward inequality. This argument also covers zero reward densities and activation exactly at a threshold.
The polynomial witness claim is correct. A subset requires one bit per supported role; its canonical coalition uses only input thresholds and zeros. Connectivity and exact rational comparison take polynomial time. Rational products and sums have polynomial bit length in the total input length.
Consequently, the complement belongs to NP and the decision problem belongs to coNP.
The invoked standard theorem is that Vertex Cover—deciding whether a finite simple undirected graph has a vertex cover of size at most an input integer \(k\)—is NP-complete. This is the source problem used as written.
The cited [Theorem 4 of Bachrach, Porat, and Rosenschein](https://arxiv.org/pdf/1402.0572) does use Vertex Cover for discrete connectivity-game hardness. The prover supplies its own thresholded reduction, so it does not assume that the discrete result automatically transfers.
The restriction to \(n\ge2\), nonempty edge set, and \(0\le k<n\) preserves hardness. Excluded instances have directly decidable answers, and restricted instances of both answer types exist. Replacing excluded inputs by fixed instances with the same answer is a routine valid preprocessing step.
Every graph requirement is satisfied:
The stated counts \(\tau=N\) and \(m=N+|F|+2\) are correct. Padding introduces actual supported roles, so the construction respects the task’s definition of support size.
All numeric requirements hold:
\(\mu_t=1/N>0\), \(\theta_t=\mu_t/2\), and \(q_t=1\). Both required normalization sums equal one.
The power-of-two choice makes the masses, thresholds, and chosen \(\epsilon\) dyadic rationals. Their individual encoding lengths are \(O(\log n)\), since \(0\le k<n\). The bound \(n\le N<2n\) ensures polynomial construction size and time.
The claimed equivalence is correct in both directions.
If neither endpoint role of an edge is selected, its primary vertex \(p_e\) has no available neighbor. It is therefore isolated and cannot connect to the distinct primary vertex \(a\). Winning consequently forces every original edge to have a selected endpoint.
Conversely, a selected endpoint of each edge supplies the stated path from \(p_e\) to \(b\). Together with the edge from \(a\) to \(b\), these paths connect all primary vertices.
Always-available primary vertices do not invalidate either implication. An uncovered edge’s primary vertex remains isolated, regardless of possible paths through other primary vertices. Padding roles cannot change this because they have no adjacency to any \(p_e\).
The cost formula \(c(S)=|S|/(2N)\) is correct. Substituting the chosen \(\epsilon\) gives
\(c(S)<1-\epsilon\) exactly when \(2|S|<2k+1\), hence exactly when \(|S|\le k\).
The integer midpoint handles strictness correctly, including \(k=0\).
A cover of size at most \(k\) yields the asserted violating canonical coalition. Conversely, any violating real coalition yields a winning subset of size at most \(k\), whose original roles form a cover of size at most \(k\). Padding cannot create a false positive because \(|C(S)|\le|S|\).
Thus the reduction maps yes-instances of Vertex Cover exactly to negative answers of the target decision problem.
The reduction proves NP-hardness of the complement. Combined with complement membership in NP, this establishes complement NP-completeness and decision coNP-completeness under polynomial-time many-one reductions.
One oracle call followed by reversal of the decision answer decides Vertex Cover. This establishes precisely the polynomial-time Turing hardness requested for the full decision-and-witness problem.
The witness obligation is also addressed: every negative instance has a feasible rational winning coalition of polynomial encoding length. The prover need not supply a polynomial-time witness-finding algorithm to establish hardness.
No repair or additional 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.