Total balancedness condition for Steiner tree games Original Research Article

In Steiner tree game associated with a graph G=(V,E), players consist of a subset N⊆V of nodes. The characteristic function value of a subset S⊆N of the players is the minimum weight of a Steiner tree that spans S. We show that it is NP-hard to determine whether a Steiner tree game is totally balanced, i.e., cores for all its subgames are non-empty. In addition, the NP-hardness result is also proven for deciding whether the core is non-empty, or whether an imputation is a member of the core.