@inbook{5dcd155762a6497fb0ed959d75925147,

title = "Fixed-parameter tractability of token jumping on planar graphs",

abstract = "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 of the same cardinality 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 fixedparameter algorithm for token jumping 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 which forbid a complete bipartite graph K3,t as a subgraph for a fixed integer t ≥ 3.",

author = "Takehiro Ito and Marcin Kami{\'n}ski and Hirotaka Ono",

note = "Publisher Copyright: {\textcopyright} Springer International Publishing Switzerland 2014.",

year = "2014",

doi = "10.1007/978-3-319-13075-0_17",

language = "English",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "208--219",

editor = "Hee-Kap Ahn and Chan-Su Shin",

booktitle = "Algorithms and Computation - 25th International Symposium, ISAAC 2014, Proceedings",

address = "Germany",

}