{
  "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 \\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 $\\mathsf{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\\to\\mathbb{R}$ and positive real constants $S,T>0$ such that $|a(v)|< \\min\\{S,T\\}$ for all $v \\in V$, and 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$. More generally, we also show that Token Jumping can be solved in time $n^{O(\\mathcal{D}(G))}$, where $\\mathcal{D}(G)$ denotes the Dilworth number of $G$. Thus, Token Jumping belongs to $\\mathsf{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).",
  "abstract_shown": true,
  "affiliations": [],
  "article_type": null,
  "arxiv": "2607.10629",
  "author_total": 1,
  "authors": [
    {
      "name": "Ziad Ismaili Alaoui"
    }
  ],
  "bibtex": "https://research.draconitic.com/paper/2bgnjj0fsq8cc.bib",
  "cited_by": 0,
  "doi": "10.48550/arxiv.2607.10629",
  "fulltext_url": null,
  "id": "2bgnjj0fsq8cc",
  "issns": [],
  "landing_url": "https://arxiv.org/abs/2607.10629",
  "language": null,
  "licence": "CC-BY-4.0",
  "licence_label": "CC BY 4.0",
  "licence_source": "article",
  "licence_url": "http://creativecommons.org/licenses/by/4.0/",
  "metadata_licence": "CC0-1.0",
  "native_subjects": [
    [
      "arxiv",
      "cs.DS"
    ],
    [
      "arxiv",
      "math.CO"
    ],
    [
      "openalex",
      "1703|Advanced Graph Theory Research"
    ]
  ],
  "openalex": "W7168267179",
  "pdf_url": "https://arxiv.org/pdf/2607.10629",
  "pmcid": null,
  "pmid": null,
  "published": "2026-09-21",
  "publisher": null,
  "ris": "https://research.draconitic.com/paper/2bgnjj0fsq8cc.ris",
  "sources": [
    {
      "first_seen": "2026-10-30T12:23:27Z",
      "native_id": "2607.10629",
      "source": "arxiv",
      "url": "https://arxiv.org/abs/2607.10629"
    }
  ],
  "subjects": [
    {
      "field": "mathematics",
      "origin": "arxiv:math.CO",
      "subfield": "combinatorics"
    }
  ],
  "title": "Independent Set Reconfiguration via Dilworth Decompositions",
  "title_text": "Independent Set Reconfiguration via Dilworth Decompositions",
  "type": "preprint",
  "updated_at": "2026-10-30T12:23:27Z",
  "url": "https://research.draconitic.com/paper/2bgnjj0fsq8cc",
  "venue": "arXiv",
  "versions": []
}