Computational complexity of a cost allocation approach to a fixed cost spanning forest problem

The authors present a computational analysis of a game theoretic approach to a cost allocation problem arising from a graph optimization problem, referred to as the fixed cost spanning forest (FCSF) problem. The customers in the FCSF problem, represented by nodes in a graph G, are in need of service that can be produced at some facilities yet to be constructed. The cost allocation problem is concerned with the fair distribution of the cost of providing the service among customers. The authors formulate this cost allocation problem as a cooperative game, referred to as the FCSF game. In general, the core of a FCSF game may be empty. However, for the case when G is a tree, it is shown that the core is not empty. Moreover, the authors prove that in this case core points can be generated in strongly polynomial time. They further provide a nonredundant characterization of the core of the FCSF game defined over a tree in the special case when all nodes are communities. This is shown to lead, in some instances, to a strongly polynomial algorithn for computing the nucleolus.