The problem {Token Jumping} asks whether, given a graph G and two independent sets of tokens I and J of G, we can transform I into J by changing the position of a single token in each step and having an independent set of tokens throughout. We show that there is a polynomial-time algorithm that, given an instance of {Token Jumping}, computes an equivalent instance of size O(g² + gk + k²), where g is the genus of the input graph and k is the size of the independent sets.
No takes yet. Share an insight, caveat, or question.
Cranston et al. (2024) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: