Metraipolis › archive › dc_5ceaeb26482b

Core stability recognition for minimum-cost spanning tree games: Parameterized perspective — arXiv:2609.18807

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.18807
License (as archived)
CC0-1.0
Archived
2026-10-15T14:08:41.701Z
SHA-256 of the archived text
4c025a6d013b3602e35db91970265e0883340f348e062aa8f8d8a0b5a36de01e
Stable URL of this page
https://metraipolis.com/documento/dc_5ceaeb26482b

How to cite

Core stability recognition for minimum-cost spanning tree games: Parameterized perspective — arXiv:2609.18807 — arXiv (en), https://arxiv.org/abs/2609.18807 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_5ceaeb26482b (Metraipolis archive dc_5ceaeb26482b, sha256 4c025a6d013b3602e35db91970265e0883340f348e062aa8f8d8a0b5a36de01e)
BibTeX
@misc{dc5ceaeb26482b,
  title = {Core stability recognition for minimum-cost spanning tree games: Parameterized perspective — arXiv:2609.18807},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.18807},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_5ceaeb26482b; sha256 4c025a6d013b3602e35db91970265e0883340f348e062aa8f8d8a0b5a36de01e},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.18807. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: economia dei servizi IA (retro-catalogo arXiv: annunci del 2026-09-17 in cs.GT).
Categorie arXiv: Computer Science and Game Theory (cs.GT) ; Computational Complexity (cs.CC).
Pagina del lavoro: https://arxiv.org/abs/2609.18807 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-15T13:50:52.124Z dalla pagina https://arxiv.org/catchup/cs.GT/2026-09-17?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).