2020-12-05T00:46:32Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmh
oai:ipsj.ixsq.nii.ac.jp:001016892020-04-01T00:33:29Z01164:02592:07425:07606
FPT algorithms for Token Jumping on GraphsFPT algorithms for Token Jumping on Graphsenghttp://id.nii.ac.jp/1001/00101667/Technical Reporthttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=101689&item_no=1&attribute_id=1&file_no=1Copyright (c) 2014 by the Information Processing Society of JapanGraduate School of Information Sciences, Tohoku UniversityDept. of Mathematics, Computer Science and Mechanics, University of WarsawFaculty of Economics, Kyushu UniversityGraduate School of Information Sciences, Tohoku UniversitySchool of Information Science, JAISTDept. of Electrical Engineering and Computer Science, Iwate UniversityTakehiro, ItoMarcin, KamińskiHirotaka, OnoAkira, SuzukiRyuhei, UeharaKatsuhisa, YamanakaSuppose 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-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-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-1482142014-06-062014-05-27