Core membership testing for minimum-cost network spanning games
Core stability recognition for minimum-cost spanning tree games: Parameterized perspective
Computer Science and Game TheoryComputational Complexity
Summary
This paper looks at a problem where different players in a network share costs for connecting to a supply point through a cheapest possible tree of paths. The key question is how to decide if a specific way of sharing costs is stable—meaning no group of players wants to change it because they could do better on their own. The authors show that this decision is hard in general but find special ways to solve it efficiently by focusing on specific graph properties or how many players have non-zero cost shares. They also design smaller equivalent problems for some types of networks to speed up the process.
What this means in practice
- •For network planners: Verify cost-sharing stability for supply networks with certain structural constraints, improving fair investment decisions in network design.
- •For software engineers: Use parameterized algorithms to efficiently check stability of cost distributions in networks, especially when graphs are close to planar or have bounded parameters.
A theory result. No direct application yet.
Authors
Michal Dvořák, Ioannis Kakatelis, Dušan Knop
Abstract
Minimum-cost spanning tree game (MSTG) is a cooperative game played on an undirected edge-weighted graph $(G,w)$ representing the network, where each vertex corresponds to a player and each edge has an associated cost~$w$. A distinguished vertex $s \in V(G)$ represents the supply or source. For any coalition of players $S$, the characteristic cost function $c(S)$ is defined as the minimum cost of a spanning tree with respect to $w$, connecting exactly the vertices in $S \cup \{s\}$. In this paper we study the computational complexity of deciding core membership for MSTG. In general, deciding whether a given allocation is in the core is \textsf{coNP}-hard~(Faigle et al.,International Journal of Game Theory,1997). We study the core recognition problem under the name {\sc MSTG Core Non-Membership}. We extend the hardness to graphs which are very close to being planar. On the positive side, we present several algorithmic results within the framework of parameterized complexity. We show that {\sc MSTG Core Non-Membership} is fixed-parameter tractable when parameterized by the support size of the allocation. Turning into structural parameters of graphs, we show that the problem admits an FPT algorithm parameterized by treewidth and signed neighborhood diversity. Last but not least, we investigate kernelization. While in general graphs, under standard complexity-theoretical assumptions, {\sc MSTG Core Non-Membership} does not admit a polynomial kernel parameterized by the vertex cover number, we design a cubic kernel in planar graphs. Furthermore, in general graphs, we obtain quadratic kernel for signed neighborhood diversity and linear kernel for the parameter feedback edge number.