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

CREATORJona Dirks, Alexandre Vigny
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE55 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-10671

Browse the full library · About the Tower of Babel