A simple quadratic kernel for Token Jumping on surfaces

2024/08/08 by Daniel W. Cranston, Moritz Mühlenthaler, Cranston, Daniel W. +3 · 1 citation
Computer Science · Physics and Astronomy · #05C69 #05C85 #Artificial Intelligence in Games #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #Experimental and Theoretical Physics Studies #FOS: Computer and information sciences

paper · pdf · doi:10.48550/arxiv.2408.04743

openalex publication_date 2024/08/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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.

Cited by

• A Linear Kernel for Independent Set Reconfiguration in Planar Graphs

Related

• Token Jumping in Planar Graphs has Linear Sized Kernels
• Fixed-Parameter Tractability of Token Jumping on Planar Graphs
• Polynomial-Time Algorithms for Sliding Tokens on Cactus Graphs and Block Graphs
• Token Sliding on Chordal Graphs
• Token Jumping in minor-closed classes