Answer: \(\mathrm{NP}\text{-complete}\), and therefore \(\mathrm{NP}\text{-hard}\)
Theorem 4 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateFor every instance of MMCP, Algorithm 3 computes an O(ln k)-approximation solution in polynomial time, where k is the number of agents. Algorithmic Framework. Our algorithm runs in rounds and adds exactly one edge to the solution H (which is ini- tially empty) in each round until the solution is feasible, i.e., it contains an MST for every agent. At the beginning of each round, every agent specifies a candidate edge set Si ⊆E\H from the unselected edges.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a connected graph G and a rational distribution over complete weak edge-ranking types, find a minimum-cardinality H subset of E such that every positive-mass type has an MST of G contained in H.
A type \(t\) is a complete weak order on \(E\), represented by ordered tie classes from cheapest to most expensive. A \(t\)-MST is a spanning tree returned by Kruskal's algorithm under this order, with ties broken arbitrarily.
The input explicitly lists a finite set \(T\) of types with rational masses \(\mu_t\ge 0\) satisfying \(\sum_{t\in T}\mu_t=1\), and an integer \(B\). Write \(T_+=\{t\in T:\mu_t>0\}\). The instance is feasible if some \(H\subseteq E\) with \(|H|\le B\) contains a \(t\)-MST for every \(t\in T_+\).
Is this distributional MMCP decision problem solvable in polynomial time, or is it NP-hard?
For a finite list of agents, the corresponding MMCP problem is NP-hard even when every agent has binary edge weights in \(\{0,1\}\). No result for the explicitly represented distribution-over-types formulation above was verified.
The explicitly represented distributional MMCP decision problem is \(\mathrm{NP}\)-complete. In particular, it is \(\mathrm{NP}\)-hard even when every positive-mass type has binary edge weights and all positive masses are equal.
For a graph \(G=(V,E)\), budget \(B\), and edge-order type \(t\), define \(P_H(t)\) to mean that \(H\subseteq E\) contains a \(t\)-MST.
Let \(t_1,\ldots,t_n\) be a finite list of agent types, and let \(U=\{t_i:i\in\{1,\ldots,n\}\}\) be the set of distinct types occurring in the list. Then, for every \(H\subseteq E\),
\[ \bigl(\forall i\in\{1,\ldots,n\},\ P_H(t_i)\bigr) \quad\Longleftrightarrow\quad \bigl(\forall t\in U,\ P_H(t)\bigr). \]
Indeed, the forward implication follows because every \(t\in U\) equals \(t_i\) for some \(i\). Conversely, every \(t_i\) belongs to \(U\), so the right-hand condition implies \(P_H(t_i)\) for every \(i\).
Thus duplicate agents impose no additional feasibility constraints. More generally, in the distributional formulation the numerical values of the positive masses are irrelevant: feasibility depends only on \(T_+\).
Use the given premise that finite-agent MMCP is \(\mathrm{NP}\)-hard even when every agent assigns each edge a weight in \(\{0,1\}\).
Consider such a finite-agent instance consisting of:
Each \(w_i\) induces a complete weak order \(t_i\): all edges of weight \(0\) form the cheapest tie class, followed by all edges of weight \(1\). Empty tie classes may simply be omitted.
Compute the set \(U=\{t_i:i\in\{1,\ldots,n\}\}\) of distinct induced types, and write \(k=|U|\). Restricting to the nonempty finite-agent instances used in the hardness result gives \(k\geq 1\).
Construct a distributional instance by setting
\[ T=U \qquad\text{and}\qquad \mu_t=\frac{1}{k} \quad\text{for every }t\in T. \]
Then every mass is positive and
\[ \sum_{t\in T}\mu_t = k\cdot\frac{1}{k} = 1. \]
Hence \(T_+=T=U\).
This construction is polynomial-time. Binary types can be represented by bit vectors of length \(|E|\), so duplicates can be removed in polynomial time. Moreover, the rational number \(1/k\) has encoding length \(O(\log k)\).
For every \(H\subseteq E\), the support-compression lemma gives
\[ H\text{ contains a }t_i\text{-MST for every agent }i \quad\Longleftrightarrow\quad H\text{ contains a }t\text{-MST for every }t\in T_+. \]
The budget is unchanged. Consequently, the finite-agent instance has a feasible cover of size at most \(B\) if and only if the constructed distributional instance does. This is a polynomial many-one reduction, proving \(\mathrm{NP}\)-hardness.
A certificate consists of:
The verifier checks that each \(\pi_t\) respects the ordered tie classes of \(t\), runs Kruskal’s algorithm in the order \(\pi_t\), and verifies that the resulting spanning tree is contained in \(H\).
These operations take polynomial time using, for example, a disjoint-set data structure. The certificate contains \(O(|T_+||E|)\) edge entries and therefore has polynomial size because all types are explicitly represented.
Thus the problem belongs to \(\mathrm{NP}\).
The distributional formulation does not become easier through aggregation into rational masses. Universal satisfaction depends only on which types have positive mass, so the known finite-agent hardness transfers after identical types are merged. The problem is therefore \(\mathrm{NP}\)-complete, and hence it is not polynomial-time solvable unless \(\mathrm{P}=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The reduction and NP-membership argument are mathematically sound in substance. The only gap is a routine edge case concerning finite-agent instances with no agents. No major issue undermines the claimed NP-completeness result.
State explicitly why the invoked finite-agent NP-hardness remains valid when there is at least one agent, or add a separate treatment of zero-agent source instances. No new structural lemma is needed.
⟨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.