On the Parameterized Complexity for Token Jumping on Graphs
On the Parameterized Complexity for Token Jumping on Graphs
复制标题
DOI：
10.1007/978-3-319-06089-7_24
复制
发表时间：
2014-04
期刊：
影响因子：
--
通讯作者：
Takehiro Ito;M. Kaminski;H. Ono;Akira Suzuki;Ryuhei Uehara;Katsuhisa Yamanaka
中科院分区：
文献类型：
--
作者：
Takehiro Ito;M. Kaminski;H. Ono;Akira Suzuki;Ryuhei Uehara;Katsuhisa Yamanaka
假设给定一个图的两个独立集合 I0 和 Ir，使得 ∣I0∣ = ∣Ir∣，并想象在 I0 中的每个顶点上放置一个标记。然后，令牌跳跃问题是确定是否存在将 I0 转换为 Irs 的独立集序列，以便通过将一个令牌恰好移动到另一个顶点来使序列中的每个独立集都是前一个独立集的结果。因此，序列中的所有独立集必须具有相同的基数。即使对于最大次数为三的平面图，该问题也是 PSPACE 完全的。在本文中，我们首先表明，当仅通过标记数量进行参数化时，该问题是 W[1]-hard 的。然后，我们给出了通用图的 FPT 算法，该算法通过标记数量和最大度进行参数化。我们的 FPT 算法可以进行修改，以便它找到 I0 和 Ir 之间独立集合的实际序列，并具有最少的令牌移动次数。
Suppose that we are given two independent setsI0andIrof a graph such that ∣I0∣ = ∣Ir∣, and imagine that a token is placed on each vertex inI0. Then, thetoken jumpingproblem is to determine whether there exists a sequence of independent sets which transformsI0intoIrso 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 PSPACE-complete even for planar graphs with maximum degree three. In this paper, we first show that the problem is W[1]-hard when parameterized only by the number of tokens. We then give an FPT algorithm for general graphs when parameterized by both the number of tokens and the maximum degree. Our FPT algorithm can be modified so that it finds an actual sequence of independent sets betweenI0andIrwith the minimum number of token movements.