Neven Villani (1), Radu Iosif (1), and Arnaud Sangnier (2)
(1) Univ. Grenoble Alpes, CNRS, Grenoble INP, VERIMAG, France
(2) DIBRIS, Università di Genova, Italy
In the standard problem of reconfiguration by token sliding, a fixed number of tokens are placed on vertices of a graph, and a move consists of sliding a token along a path that does not contain any other tokens. The task is to decide if a target configuration is reachable from a given initial configuration. Several variations exist to the problem, notably whether or not the support graph is directed (if so, tokens can slide only along oriented edges, otherwise every move is reversible), and whether or not the tokens are distinguishable (if so, the initial and target configurations impose which specific token should be on a given vertex, otherwise only the presence of any token is required). Our focus is on the version with both directed edges and distinguished tokens, which is a generalization of all other cases, but is much less well-understood.
Furthermore we investigate the decidability of this reachability problem not on a single graph but on a potentially infinite set of graphs described by a context-free grammar in the style of Courcelle. This gives rise to a parameterized version of the problem where the question is if all/any of an infinite family of graphs and their respective configurations are reachable by token sliding.
To that end we exhibit a cutoff: we prove that a target configuration is reachable if and only if it is reachable within a number of moves that depends only on the number of tokens, independently of the size of the graph. We show that this implies that a solution to the problem can be expressed in the Monadic Second-Order logic for graphs, which in turn implies that it is decidable in parameterized families. Our cutoff is based on successive decompositions of a graph: every graph can be seen as an acyclic graph of strongly connected components, themselves decomposable into a tree of collections of cycles of length at least 3. For each of those successive layers we prove properties of the graph of local configurations, to finally prove a global bound on the diameter of the graph of all possible configurations.