arXiv:2010.08936 · v4
Arboricity games: the core and the nucleolus
摘要
The arboricity of a graph is the minimum number of forests required to cover all its edges. In this paper, we examine arboricity from a game-theoretic perspective and investigate cost-sharing in the minimum forest cover problem. We introduce the arboricity game as a cooperative cost game defined on a graph. 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 not empty. In order to compute the nucleolus in the core, we introduce the prime partition which is built on the lattice of maximum-density edge sets. The prime partition decomposes the edge set of a graph into a non-prime set and a partially ordered collection of prime sets defined from minimal densest minors and their invariant precedence relation. Moreover, edges from the same set of the partition always have the same value in a core allocation. Consequently, when the core is not empty, the prime partition significantly reduces the number of variables and constraints required in the linear programs of Maschler's scheme and allows us to compute the nucleolus in polynomial time. Besides, the prime partition provides a graph decomposition analogous to the celebrated core decomposition and the density-friendly decomposition, which may be of independent interest.
作者备注：Corrections and clarifications to proof details and exposition; main results and conclusions unchanged
期刊信息：Mathematical Programming 198, 1-25 (2023)