CS Paper Radar

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

Michal Dvořák, Ioannis Kakatelis, Dušan Knop

cs.GT cs.CC ·submitted 2026-09-16 15:20 UTC · v2

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Matroid Packing Games: The Core and the Nucleolus

cs.GT ·2026-09-29 ·Pengfei Liu, Han Xiao, Xin Chen, Qizhi Fang
similarity 0.69
Abstract · Accepted at WINE 2026. A one-page extended abstract will appear in the conference proceedings. This is the full version

In this paper, we study the matroid base packing problem from the perspective of cooperative game theory and define the associated matroid base packing game. This model extends the network strength game of Baiou and Barahona (2020) from graphic matroids to general matroids. Building on the exchange structure of matroid, we develop a graph theoretic framework for analyzing the core and the nucleolus in this game. This framework yields a compact characterization of core nonemptiness and enables polynomial time algorithms for testing core nonemptiness, finding a core allocation, and computing the nucleolus. In particular, the approach provides a broader and more structured framework for the nucleolus computation problem arising in network strength games studied by Baiou and Barahona (2020), covering both the nonempty core and empty core cases.

0.15

Fair, Efficient and Connected Allocations on Graphs

cs.GT ·2026-08-19 ·Susobhan Bandopadhyay, Anish Datta, Palash Dey, Ashlesha Hota, Abhishek Sahu
published similarity 0.64
Abstract · Accepted to Algorithmic Decision Theory (ADT) 2026, Paris, France

We study the classical and parameterized complexity of efficient connected allocation problems on graphs, where efficiency is measured by egalitarian and utilitarian welfare maximization. We first establish a sharp complexity dichotomy in the classical setting: both problems are NP-hard in general and remain hard even on very restricted graph classes such as paths, and consequently trees and cycles. In contrast, they are polynomial-time solvable on stars, but this tractability does not extend even to the case of two disjoint stars. Motivated by these boundaries, we move to the parameterized complexity framework, where we study the problem with respect to the number of agents. We obtain fixed-parameter tractability (FPT) on trees and, more generally, identify a robust phenomenon whereby tractability on a connected graph class extends to disjoint unions of graphs from that class. We further investigate the parameters treewidth and treedepth, showing that the utilitarian version is FPT for both, whereas the egalitarian version remains para-NP-hard even on graphs of treedepth two. Finally, we analyze the number of connected components and show that except for the collection of stars, the problems remain hard. For the collection of stars,while we obtain para-NP-hardness for the egalitarian case, the utilitarian case gives W[2]-hardness together with an XP algorithm.

0.25

Antichains for Concurrent Parameterized Games

cs.LO ·2026-10-08 ·Nathalie Bertrand, Patricia Bouyer, Gaëtan Staquet
published similarity 0.63
Abstract · In Proceedings GandALF 2026, arXiv:2610.08898. A full version of this paper, containing all proofs, appears at arXiv:2505.13460

Concurrent parameterized games involve a fixed yet arbitrary number of players. They are described by finite arenas in which the edges are labeled with languages that describe the possible move combinations leading from one vertex to another (n players yield a word of length n). Previous work showed that, when edge labels are regular languages, one can decide whether a distinguished player, called Eve, has a strategy to ensure a reachability objective, against any strategy profile of her arbitrarily many opponents. This decision problem is known to be PSPACE-complete. A basic ingredient in the PSPACE-membership proof is the reduction to the exponential-size knowledge game, a 2-player game that reflects the knowledge Eve has on the number of opponents. In this paper, we provide a symbolic approach, based on antichains, to compute Eve's winning region in the knowledge game. In words, it gives the minimal knowledge Eve needs at every vertex to win the concurrent parameterized reachability game. More precisely, we propose two fixed-point algorithms that compute, as an antichain, the maximal elements of the winning region for Eve in the knowledge game. We implemented these two algorithms in C++, as well as the one initially proposed, and report on their relative performances on various benchmarks.

0.46

A Deterministic $(2+\varepsilon)$-Approximation for Weighted Feedback Vertex Set in Tournaments

cs.DS ·2026-09-14 ·Hanqing Li, Zihan Wu
theory similarity 0.62
Abstract · 8 pages, no figures

We study the weighted feedback vertex set problem in tournaments. For every fixed integer $k\geq 2$, we give a deterministic $(2+1/k)$-approximation algorithm with running time $n^{2^{O(k)}}$, apart from polynomial dependence on the encoding length of the weights. Consequently, for every fixed $\varepsilon>0$, weighted feedback vertex set in tournaments has a deterministic $(2+\varepsilon)$-approximation running in time $n^{2^{O(1/\varepsilon)}}$. The algorithm combines two ingredients. When the triangle graph of the tournament has bounded clique number, a chain decomposition of its transitive complement yields an exact dynamic program for a maximum-weight transitive subtournament. When the clique number is large, a structural theorem for triangle graphs supplies a constant-size strongly good cost vector. A local-ratio reduction with this cost vector gives the claimed guarantee. As a by-product, the dynamic program solves weighted feedback vertex set exactly in $\mathcal B_7$-free tournaments in time $O(n^7)$, where $\mathcal B_7$ is the family of seven-vertex tournaments with feedback vertex set number at least three.

0.27

Individual Rationality in Constrained Hedonic Games: Friends, Enemies, and Neutrals

cs.GT ·2026-08-14 ·Šimon Schierreich, Ildikó Schlotter
publishedtheory similarity 0.61
Abstract

We study constrained coalition formation in games induced by friends, enemies, and neutrals, under the two standard refinements of additively separable preferences: friend-oriented and enemy-oriented. We ask for partitions that are individually rational (IR), while additionally requiring exactly $k$ non-empty coalitions, each satisfying a prescribed lower and upper bound on its size. Although IR alone is trivial to satisfy for any hedonic game, the size constraints make it computationally intractable to decide whether a feasible partition exists. The two models tell strikingly different stories. Under enemy-oriented preferences, the problem collapses to size-constrained graph coloring, and its complexity follows accordingly. Under friend-oriented preferences, however, the picture is far more intricate, and is governed by the enmity structure rather than the friendships. The complexity is further shaped by two factors: how strict the imposed size requirements are, and whether relationships are symmetric or asymmetric, with several cases turning out tractable in the symmetric setting but intractable once asymmetry is allowed. Charting this boundary in terms of both classical and parameterized complexity, we provide a complete understanding of which properties of the friend/enemy structure are responsible for hardness.

0.23

Parameterized Complexity of Temporal Agony

cs.DS ·2026-08-20 ·Tom-Lukas Breitkopf, Vincent Froese, Anton Herrmann, Pascal Kunz
publishedhot direction similarity 0.61
Abstract · To appear at ALGOWIN 2026

Real-world networks are often organized in several layers forming a hierarchy which determines the interaction between the individual components. In order to discover such hierarchies in temporal networks, Tatti [ECML PKDD 2018] introduced the temporal agony problem Seg-Agony. Here, the goal is to assign each vertex a certain rank (from 1 to $k$) such that arcs only point from lower ranks to higher ranks. Backward arcs are penalized depending on the difference between the corresponding ranks. Since arcs may change over time, each vertex is allowed to change its rank $\ell\ge 1$ times in order to minimize the overall penalty $α$ (called temporal agony). We study the parameterized complexity of Seg-Agony with a special focus on the number $k$ of possible ranks for which we identify the precise complexity border. We show that the problem is polynomial-time solvable for $k=2$, NP-hard for $k=3$ and $\ell=1$ but polynomial-time solvable for constant $α$, and NP-hard for $k=4$ and $\ell=1$ even for $α=0$. We further show a polynomial-time algorithm for a constant number $n$ of vertices and fixed-parameter tractability for the combined parameter $n+\ell$.

0.37

The Complexity of Undirected Partizan Edge Geography

cs.DS math.CO ·2026-09-16 ·Yuto Okada
similarity 0.61
Abstract · 9 pages, 6 figures

Partizan Edge Geography is a two-player game on a graph where each player has their own token on a vertex and moves their token to a neighbor in a turn removing the edge. Two player alternately move their tokens and the first player who cannot move loses the game. Fraenkel and Simonson (TCS, 1993) showed that the winner determination of this game is PSPACE-complete on directed graphs, given a graph and token positions. This paper resolves its complexity on undirected graphs by showing the PSPACE-completeness on bipartite undirected graphs of maximum degree 3. The same reduction also works for a variant where two tokens cannot be placed on the same vertex.

0.52

Algorithms with Smoothed Polynomial-Time Complexity for Deterministic Discounted-sum and Mean-payoff Games

cs.GT cs.DS ·2026-10-09 ·Ali Asadi, Krishnendu Chatterjee, Ruichen Luo
similarity 0.61
Abstract

Turn-based deterministic games on graphs are two-player zero-sum games played on finite directed graphs, where the vertex set is partitioned between the Max and the adversarial Min Player. The respective player chooses outgoing edges from their vertices. We consider these games with the classical discounted-sum and mean-payoff objectives. The goal of the Max Player is to maximize the objective against the adversarial Min Player. These games lie in NP $\cap$ coNP and are among the rare combinatorial problems that belong to this complexity class, yet the existence of a polynomial-time algorithm is a major open question. All known deterministic algorithms require exponential time in the worst case, while the classical strategy iteration (policy iteration) algorithm is remarkably efficient in practice, which motivates the study of the smoothed complexity of these games. Previous results established a smoothed polynomial-time bound only for the restricted class of ergodic games and presented only a high-probability guarantee. Our main result is a new analysis technique for a variant of the strategy iteration algorithm, and we show these algorithms achieve smoothed polynomial complexity for general game graphs with both high-probability and expected runtime guarantees. In particular, our result removes the ergodicity restriction of prior work and strengthens the high-probability guarantee to the stronger expected-runtime guarantee, thereby resolving the open question on the smoothed complexity of these games.

0.50