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 KN the complete graph on the node set N∪{0}. Assume that the edges of KN have nonnegative weights and associate with each coalition S⊆N of players as cost c(S) the weight of a minimal spanning tree on the node set S∪{0}. Using transformation from EXACT COVER BY 3-SETS, we exhibit the following problem to be NP-complete. Given the vector x∈ℜ^N with x(N) = c(N), decide whether there exists a coalition S such that x(S) > c(S).