Arboricity Games: the Core and the Nucleolus

The arboricity of a graph is the minimum number of forests needed to cover all edges of the graph. In this paper, we study the arboricity from a game theoretic perspective and consider cost sharing in the minimum forest cover problem. We introduce the arboricity game as a cooperative cost game defined on a graph, where the players are edges and the cost of each coalition is the arboricity of the subgraph induced by the coalition. We study properties of the core and propose an efficient algorithm for computing the nucleolus when the core is nonempty. To compute the nucleolus, we introduce the prime partition of a graph, which decomposes the edge set into a partially ordered set defined from all minimal densest minors and their invariant precedence relation. For any core allocation of arboricity games, all edges from the same set of the prime partition share the same value. Thus the prime partition enables us to simplify the variables and constraints in linear programs of Maschler's scheme and to compute the nucleolus of arboricity games in polynomial time when the core is nonempty. Besides, the prime partition provides an analogous graph decomposition to the celebrated core decomposition and the density-friendly decomposition, which may be of independent interest.