Independent Set Reconfiguration on Threshold Signed Graphs
2026-07-12 • Data Structures and Algorithms
Data Structures and Algorithms
AI summaryⓘ
The authors study two puzzles called Token Jumping and Sliding Token where you need to move tokens on a graph from one arrangement to another without breaking certain rules. They focus on a special type of graph called threshold signed graphs, which have a unique mathematical structure. They show that for these graphs, both puzzles can be solved efficiently using a new algorithm. This expands what is known about when these problems are easy or hard to solve in different types of graphs.
Token JumpingSliding TokenIndependent SetThreshold Signed GraphPermutation GraphPSPACE-completePolynomial-time AlgorithmGraph ReconfigurationInclusion-chain Structure
Authors
Ziad Ismaili Alaoui
Abstract
The Token Jumping and Sliding Token problems are fundamental reconfiguration problems defined on the independent sets of an undirected graph. Given two independent sets $I$ and $J$, each of size $k$, these problems ask whether there exists a sequence of elementary operations transforming $I$ into $J$ such that every intermediate configuration is also an independent set of size $k$. In Sliding Token, an operation moves a token from a vertex $u \in I$ to an adjacent vertex $v \notin I$; in Token Jumping, the token may instead move to any vertex $v \notin I$. While both problems are PSPACE-complete on general graphs, polynomial-time algorithms have been developed for several graph classes, including trees, block graphs, cacti, bipartite permutation graphs, cographs, $P_4$-tidy graphs, and interval graphs. In this paper, we prove that both problems are solvable in polynomial time on threshold signed graphs, also known as Dilworth-2 graphs. A graph $G=(V,E)$ is a threshold signed graph if there exist a mapping $a:V\to\mathbb{R}$ and positive real constants $S$ and $T$ such that, for any distinct vertices $u,v\in V$, $\{u,v\}\in E$ if and only if $|a(u)+a(v)|\ge S$ or $|a(u)-a(v)|\ge T$. This graph class is a subclass of permutation graphs, for which the complexity of these problems remains open, and is incomparable with the class of bipartite permutation graphs studied by Fox-Epstein et al. (ISAAC, 2015). The algorithm is based on the inclusion-chain structure that characterises threshold signed graphs, a structural property that may be of independent interest.