Token Sliding Reconfiguration on DAGs
Jona Dirks, Alexandre Vigny · 2025
Read Token Sliding Reconfiguration on DAGs by Jona Dirks, Alexandre Vigny (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-10671.txt.
Description
Jona Dirks and Alexandre Vigny study a puzzle of sliding tokens in 2025 on directed graphs. Tokens sit on points of a graph, no two sharing an edge, and a token may slide along an edge to a free point. The question is whether one valid setup can be morphed into another, step by step. On directed graphs with a flow order, called DAGs, the answer was open.
The pair draw a sharp line by depth. At depth three the problem is fully hard in the classic sense. At depth four it is hard in a finer sense tied to the number of tokens. With extra limits on the graph's tree-like width, it becomes tractable. Their bounds are tight, so the map of this problem is now complete for DAGs.
Catalog record
| CREATOR | Jona Dirks, Alexandre Vigny |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 55 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-10671