http://swrc.ontoware.org/ontology#TechnicalReport
FPT algorithms for Token Jumping on Graphs
en
Graduate School of Information Sciences, Tohoku University
Dept. of Mathematics, Computer Science and Mechanics, University of Warsaw
Faculty of Economics, Kyushu University
Graduate School of Information Sciences, Tohoku University
School of Information Science, JAIST
Dept. of Electrical Engineering and Computer Science, Iwate University
Takehiro Ito
Marcin Kamiński
Hirotaka Ono
Akira Suzuki
Ryuhei Uehara
Katsuhisa Yamanaka
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.
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.
AN1009593X
研究報告アルゴリズム（AL）
2014-AL-148
2
1-4
2014-06-06