Various least core concepts including the classical least core of cooperative games are discussed. By a reduction from minimum cover problems, we prove that computing an element in these least cores is in general NP-hard for minimum cost spanning tree games. As a consequence, computing the nucleolus, the nucleon and the per-capita nucleolus of minimum cost spanning tree games is also NP-hard.
- Spanning tree
- least core
- Cooperative game
Faigle, U., Kern, W., & Paulusma, D. (2000). Note on the computational complexity of least core concepts for min-cost spanning tree games. Mathematical methods of operations research, 2000(52), 23-38. https://doi.org/10.1007/s001860000059