FPT algorithms for Token Jumping on Graphs

概要

論文の詳細を見る
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. Then, 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. Therefore, all independent sets in the sequence must be of the same cardinality. This problem is W[1]-hard when parameterized only by the number of tokens. In this paper, we give FPT algorithms for general graphs when parameterized by both the number of tokens and the maximum degree.
2014-06-06