Token reconfiguration

In computational complexity theory and combinatorics, the token reconfiguration problem is a reconfiguration problem on a graph with both an initial and desired state for tokens.

Given a graph ${\displaystyle G}$, an initial state of tokens is defined by a subset ${\displaystyle V\subset V(G)}$ of the vertices of the graph; let ${\displaystyle n=|V|}$. Moving a token from vertex ${\displaystyle v_{1}}$ to vertex ${\displaystyle v_{2}}$ is valid if ${\displaystyle v_{1}}$ and ${\displaystyle v_{2}}$ are joined by a path in ${\displaystyle G}$ that does not contain any other tokens; note that the distance traveled within the graph is inconsequential, and moving a token across multiple edges sequentially is considered a single move. A desired end state is defined as another subset ${\displaystyle V'\subset V(G)}$. The goal is to minimize the number of valid moves to reach the end state from the initial state.^[1]