On the Complexity of Testing Membership in the Core of Min-Cost Spanning Tree Games

Let $N=\{ 1,...,n\} $ be a finite set of players and $K_{N}$ the complete graph on the node set $N\cup \{ 0\} $. Assume that the edges of $K_{N}$ have nonnegative weights and associate with each coalition $S\subseteq N$ of players as cost $c(S)$ the weight of a minimal spanning tree on the node set $S\cup \{ 0\} $. <p>Using transformation from EXACT COVER BY 3-SETS, we exhibit the following problem to be NP-complete. Given the vector $x\in R^{N}$ with $x(N)=c(N)$. Decide whether there exists a coalition S such that $x(S) > c(S)$.