2014/06/25 by Takehiro Ito, Marcin Kamiński, Ito, Takehiro +3 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Algorithms and Data Compression #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1406.6567
openalex publication_date 2014/06/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Suppose that we are given two independent sets I0 and Ir of a graph such that |I0| = |Ir|, and imagine that a token is placed on each vertex in I0. The token jumping problem is to determine whether there exists a sequence of independent sets which transforms I0 into Ir so that each independent set in the sequence results from the previous one by moving exactly one token to another vertex. This problem is known to be PSPACE-complete even for planar graphs of maximum degree three, and W[1]-hard for general graphs when parameterized by the number of tokens. In this paper, we present a fixed-parameter algorithm for the token jumping problem on planar graphs, where the parameter is only the number of tokens. Furthermore, the algorithm can be modified so that it finds a shortest sequence for a yes-instance. The same scheme of the algorithms can be applied to a wider class of graphs, K3,t-free graphs for any fixed integer t ≥ 3, and it yields fixed-parameter algorithms.