{"ID":6536160,"CreatedAt":"2026-07-14T01:21:01.169441415Z","UpdatedAt":"2026-07-15T03:28:55.185153975Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2607.10629","arxiv_id":"2607.10629","title":"Independent Set Reconfiguration on Threshold Signed Graphs","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.","short_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 in...","url_abs":"https://arxiv.org/abs/2607.10629","url_pdf":"https://arxiv.org/pdf/2607.10629v1","authors":"[\"Ziad Ismaili Alaoui\"]","published":"2026-07-12T07:42:47Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"math.CO\"]","methods":"[]","has_code":false}