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 densest subgraph lattice. The prime partition decomposes the edge set of a graph into a partially ordered set defined from minimal densest minors and their invariant precedence relation. Moreover, edges from the same 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.
翻译:图形的偏差度是覆盖其所有边缘所需的最小森林数量。 在本文中, 我们从游戏理论角度来检查偏差度, 并调查最小森林覆盖问题的成本分担问题 。 我们将偏差率游戏引入为图表上定义的合作成本游戏 。 玩家是边缘, 每个联盟的成本是联盟引出的子层的偏差 。 我们研究核心的属性, 并提出在核心不空时计算核核糖核的高效算法 。 为了计算核心核核糖核, 我们从游戏理论角度来研究偏差, 并调查最小森林覆盖问题的最低森林覆盖问题的成本分担 。 我们引入主要分区将图表的边缘转换为部分定序, 由最小密度的未成年人和他们的惯性优先关系来定义 。 此外, 同一分区的边缘在核心分配中总是具有相同的价值 。 因此, 如果核心不是空的, 则主要分区会大大减少毛列核心内线性程序所需的变量和限制数量 。 我们的最小值分配 。