A Simple Quadratic Kernel for Token Jumping on Surfaces
摘要
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 + k)^2)\) , where g is the genus of the input graph and k is the size of the independent sets. Our algorithm is very simple and does not require any information about the genus of the input graph.