Answer: In \(\mathrm{P}\): every valid instance is a YES-instance, and the minimum removal cost is \(0\). Decision takes \(O(L)\) time including reading the input.
Theorem 8 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateThe problem of finding a minimum-weight vertex-removal stabilizer is NP-hard. We reduce the clique problem (CLIQUE), which is defined as follows. Input. A graph G′ and a positive integer p.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite type set \(T\), a compatibility graph \(H=(T,F)\), rational type masses \(\mu_t\) summing to \(1\), and nonnegative rational removal costs \(w_t\), choose removed masses \(r_t\in[0,\mu_t]\) to minimize \(\sum_{t\in T} w_t r_t\). For the remaining masses \(q_t=\mu_t-r_t\), the society is stable if there are nonnegative type payoffs \(p_t\) with \(p_t+p_u\ge1\) for each \(\{t,u\}\in F\), and \(\sum_t q_t p_t\) equals the maximum matching mass \(\max\sum_{\{t,u\}\in F}x_{tu}\), subject to \(\sum_{u:\{t,u\}\in F}x_{tu}\le q_t\) for each \(t\) and \(x_{tu}\ge0\). Find a minimum-cost stabilizing removal.
A society is given by its support: a list \(T\) of \(\tau=|T|\) 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 compatibility graph \(H=(T,F)\) is simple and undirected; each compatible pair produces unit value. Let \(m=|F|\). Removal costs \(w_t\) and a budget \(B\) are nonnegative binary rationals; \(L\) is the total input bit length.
Choose real removed masses \(0\le r_t\le\mu_t\), costing \(\sum_{t\in T}w_t r_t\), and put \(q_t=\mu_t-r_t\). Remaining masses are not renormalized; removing the entire society is allowed.
Define the maximum matching mass by \(M(q)=\max\{\sum_{\{t,u\}\in F}x_{tu}:x\in\mathbb R_{\ge0}^{F},\ \sum_{u:\{t,u\}\in F}x_{tu}\le q_t\text{ for every }t\in T\}\).
The remaining society is stable if there exist real payoffs \(p_t\ge0\) satisfying \(p_t+p_u\ge1\) for every \(\{t,u\}\in F\) and \(\sum_{t\in T}q_t p_t=M(q)\). Payoffs for zero-mass types are auxiliary variables and contribute nothing to this sum.
The decision problem asks whether a stable removal of cost at most \(B\) exists.
Is this continuous stabilizing-removal decision problem in P or NP-hard, with running times measured in \(m\), \(\tau\), and \(L\)?
For finite agents, minimum-cost vertex removal yielding a matching game with nonempty core is NP-hard; minimizing the number of removed vertices is polynomial-time solvable ([discrete results](https://www.ifaamas.org/Proceedings/aamas2016/pdfs/p41.pdf)).
No prior result settling this exact continuous formulation was identified in the literature search.
The stated decision problem is in \( \mathrm{P} \). In fact, every valid instance is a YES-instance, and the minimum removal cost is \(0\).
I use exactly the stated definition of \(M(q)\), with real edge masses. Under this definition, stability is automatic for every remaining mass vector. This follows from linear-programming duality, including when some types have zero mass.
Fix any vector \(q\) satisfying \(0\le q_t\le\mu_t\). Let \(A\) be the vertex-edge incidence matrix of \(H\): the column corresponding to \(\{t,u\}\) has a \(1\) in rows \(t,u\) and zeros elsewhere. Then the program defining matching mass is
\(M(q)=\max\{\mathbf{1}^{\mathsf T}x:Ax\le q,\ x\ge0\}.\)
This program is feasible because \(x=0\) is feasible. Summing its vertex constraints gives
\(2\sum_{e\in F}x_e=\sum_{t\in T}(Ax)_t\le\sum_{t\in T}q_t\le1.\)
Thus its objective is bounded. Its feasible set is also compact: every edge variable satisfies \(0\le x_{\{t,u\}}\le\min(q_t,q_u)\), and all constraints are closed. Consequently, the maximum is attained. When \(F\) is empty, the unique empty edge vector gives value \(0\).
The linear-programming dual is
\(\min\{\sum_{t\in T}q_t p_t:p_t\ge0,\ p_t+p_u\ge1\text{ for every }\{t,u\}\in F\}.\)
To verify this dual explicitly, the constraint \(Ax\le q\) supplies one nonnegative dual variable \(p_t\) per type. Each edge variable supplies the constraint \((A^{\mathsf T}p)_{\{t,u\}}=p_t+p_u\ge1\).
The dual is feasible: take \(p_t=1\) for every type. Its minimum is attained even when some \(q_t=0\). Indeed, given any dual-feasible \(p\), define \(\widehat p_t=\min(p_t,1)\). For each edge:
Hence \(\widehat p\) remains feasible. Since \(q_t\ge0\), clipping cannot increase the objective. We may therefore minimize over the nonempty compact feasible subset of \([0,1]^T\), where the continuous objective attains its minimum.
Strong duality applies to these feasible, finite linear programs. Therefore an optimal dual vector \(p^*\) satisfies
\(p^*_t\ge0,\qquad p^*_t+p^*_u\ge1\text{ for every }\{t,u\}\in F,\qquad \sum_{t\in T}q_t p^*_t=M(q).\)
These are precisely the stated stability conditions. Zero-mass types cause no exception: their variables still satisfy the edge constraints and contribute zero to the objective.
Choose \(r_t=0\) for every \(t\). Then \(q=\mu\), which is stable by the preceding proof, and the removal cost is
\(\sum_{t\in T}w_t r_t=0\le B.\)
Every permitted removal has nonnegative cost because \(w_t,r_t\ge0\). Thus the optimal removal cost is exactly \(0\).
On the promised valid input domain, the decision algorithm simply returns YES. Including reading the input, it runs in \(O(L)\) time; no graph optimization is required.
If explicit stable payoffs are requested, solve the dual at \(q=\mu\). It has \(\tau\) variables and \(m+\tau\) inequalities, with rational encoding length polynomial in \(m,\tau,L\). Polynomial-time rational linear programming therefore produces a rational payoff witness in \(\operatorname{poly}(m,\tau,L)\) bit time.
The discrete matching game uses the maximum integral matching value. Its core can be empty because the fractional matching value exceeds the integral value. The cited paper explicitly characterizes discrete stability by equality of those two values. [Ito et al., *Efficient Stabilization of Cooperative Matching Games*, Section 2](https://www.ifaamas.org/Proceedings/aamas2016/pdfs/p41.pdf).
For example, a triangle has integral matching number \(1\). Assigning \(1/2\) to each edge gives fractional value \(3/2\), which is optimal by summing the three capacity constraints.
In the present formulation, the welfare benchmark is already the fractional program. Its dual optimum therefore always provides the required payoffs. This argument applies to arbitrary compatibility graphs, including graphs with odd cycles.
⟨structured verdict parsed — rendered above⟩
The proof is correct and resolves the stated task. Every valid instance admits a stable removal of cost \(0\), so the decision problem is in \(\mathrm{P}\). No major or minor mathematical issues were found.
The conclusion uses the task’s explicit real-valued definition of matching mass and its explicit stability conditions. It does not depend on a degenerate interpretation of the removal budget or the masses.
The incidence matrix \(A\) correctly represents the capacity constraints. Because the graph is simple and undirected, each edge column has exactly two entries equal to \(1\). Thus the displayed linear program is precisely the definition of \(M(q)\).
The zero vector is feasible because every \(q_t\) is nonnegative. Summing the vertex constraints correctly yields
\[
2\sum_{e\in F}x_e\le\sum_{t\in T}q_t\le1.
\]
The coordinate bound \(x_{\{t,u\}}\le\min(q_t,q_u)\) also follows directly from nonnegativity and the two endpoint constraints. Consequently, the feasible set is closed and bounded in a finite-dimensional space, hence compact, and the objective attains its maximum. The empty-edge case is explicitly and correctly handled.
For the primal maximization problem with constraints \(Ax\le q\) and \(x\ge0\), the dual has nonnegative variables \(p\), objective \(q^{\mathsf T}p\), and constraints \(A^{\mathsf T}p\ge\mathbf1\). These are exactly
\[
p_t\ge0,\qquad p_t+p_u\ge1
\]
for every compatible pair. There is no missing constraint or incorrect sign.
Taking every payoff equal to \(1\) proves feasibility. The clipping argument is valid: if an endpoint is clipped, its new payoff is \(1\), while the other endpoint remains nonnegative; otherwise the edge constraint is unchanged. Because \(q_t\ge0\), clipping cannot increase the objective. Restriction to the nonempty compact feasible subset of \([0,1]^T\) therefore preserves the infimum and ensures attainment. This argument remains valid when some or all remaining masses are zero.
The invoked theorem is finite-dimensional linear-programming strong duality: feasible primal and dual programs with finite optimal values have equal optimal values. The write-up verifies these hypotheses and establishes attainment on both sides. Hence the optimal dual payoff vector satisfies every stated stability condition, including the equality with \(M(q)\). The universal claim covers every permitted real remaining-mass vector, without requiring it to be rational.
The choice \(r_t=0\) satisfies all removal bounds and costs \(0\le B\). Stability follows from the preceding argument with \(q=\mu\). Nonnegative costs and removals exclude any smaller objective value, so the optimum is exactly \(0\). Returning YES on the promised valid domain is correct, and reading the input takes \(O(L)\) time. The optional payoff computation also fits polynomial-time rational linear programming: its dimensions and coefficient encoding lengths are polynomial in \(m,\tau,L\).
The cited characterization is accurate: Section 2, Proposition 1 states that a discrete graph is stable exactly when its integral and fractional matching numbers coincide. [Ito et al., *Efficient Stabilization of Cooperative Matching Games*](https://www.ifaamas.org/Proceedings/aamas2016/pdfs/p41.pdf). The triangle calculation is correct for the unit vertex capacities used in that discrete comparison. This explanatory example is separate from the normalized continuous instance and introduces no inconsistency.
None. The proof establishes the claimed decision result and minimum removal cost.
⟨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.