Independent Set Reconfiguration via Dilworth Decompositions
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. Suppose a token is placed on each vertex of I: in Sliding Token, an operation moves a token from a vertex u ∈ I to an adjacent vertex v ∉ I; in Token Jumping, the token may instead move to any vertex v ∉ I. While both problems are PSPACE-complete on general graphs, polynomial-time algorithms for one or both variants have been developed for several graph classes, including trees, block graphs, bipartite permutation graphs, cographs, P4-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→ℝ and positive real constants S,T>0 such that |a(v)|< min{S,T} for all v ∈ V, and for any distinct vertices u,v∈ V, {u,v}∈ E if and only if |a(u)+a(v)|≥ S or |a(u)−a(v)|≥ T. More generally, we also show that Token Jumping can be solved in time nO(𝒟(G)), where 𝒟(G) denotes the Dilworth number of G. Thus, Token Jumping belongs to XP when parameterised by the Dilworth number. 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).
Related
- Independent Backward Preimages and Algebraic Radial Decompositions of Operators
- Stable Set Reconfiguration in Dense Digraphs
- Mostow-Type Decompositions and Geometric Means for Symmetric Cones
- Decompositions of CSBPs via Poissonian Intertwining
- Venusian Radio Occultation Constellation Design and Reconfiguration Problems: A Benders Decomposition Approach
BibTeX
@misc{alaoui2026independent,
title = {{Independent Set Reconfiguration via Dilworth Decompositions}},
author = {Ziad Ismaili Alaoui},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2607.10629},
eprint = {2607.10629},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2607.10629},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Independent Set Reconfiguration via Dilworth Decompositions
AU - Ziad Ismaili Alaoui
PY - 2026
DA - 2026/09/21
PB - arXiv
DO - 10.48550/arxiv.2607.10629
UR - https://arxiv.org/abs/2607.10629
AB - 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. Suppose a token is placed on each vertex of I: in Sliding Token, an operation moves a token from a vertex u ∈ I to an adjacent vertex v ∉ I; in Token Jumping, the token may instead move to any vertex v ∉ I. While both problems are PSPACE-complete on general graphs, polynomial-time algorithms for one or both variants have been developed for several graph classes, including trees, block graphs, 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→ℝ and positive real constants S,T>0 such that |a(v)|< min{S,T} for all v ∈ V, and for any distinct vertices u,v∈ V, {u,v}∈ E if and only if |a(u)+a(v)|≥ S or |a(u)−a(v)|≥ T. More generally, we also show that Token Jumping can be solved in time n^O(𝒟(G)), where 𝒟(G) denotes the Dilworth number of G. Thus, Token Jumping belongs to XP when parameterised by the Dilworth number. 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).
ER -