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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

A Simple Quadratic Kernel for Token Jumping on Surfaces

  • Daniel W. Cranston,
  • Moritz Mühlenthaler,
  • Benjamin Peyrille

摘要

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.