Parameterized complexity of independent set reconfiguration problems
Parameterized complexity of independent set reconfiguration problems
复制标题
独立集重构问题的参数化复杂度
DOI：
10.1016/j.dam.2020.01.022
复制
发表时间：
2020
影响因子：
1.1
通讯作者：
Yamanaka Katsuhisa
中科院分区：
文献类型：
--
作者：
Ito Takehiro;Kaminski Marcin;Ono Hirotaka;Suzuki Akira;Uehara Ryuhei;Yamanaka Katsuhisa
假设给我们两个独立的图集 I 0 和 I r ，使得 |我0|=| I r|，并想象在 I 0 中的每个顶点上放置一个令牌。然后，令牌跳跃问题是确定是否存在将 I 0 转换为 I r 的独立集序列，使得序列中的每个独立集都是通过将一个令牌恰好移动到另一个顶点而从前一个独立集产生的。因此，序列中的所有独立集必须具有相同的基数。即使对于最大次数为三的平面图，该问题也是 PSPACE 完全的。在本文中，我们首先表明，当仅通过标记数量进行参数化时，该问题是 W [1]-困难的。然后，我们给出了通用图的 FPT 算法，该算法通过标记数量和最大度进行参数化。我们的 FPT 算法可以进行修改，以便它以最少的令牌移动次数找到 I 0 和 I r 之间的独立集合的实际序列。我们最终表明，令牌跳跃的结果之一可以扩展到独立集的更广义的重新配置问题，称为令牌添加和删除。
Suppose that we are given two independent sets I 0 and I r of a graph such that| I 0|=| I r|, and imagine that a token is placed on each vertex in I 0. Then, the token jumping problem is to determine whether there exists a sequence of independent sets which transforms I 0 into I r 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 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 between I 0 and I r with the minimum number of token movements. We finally show that one of the results for token jumping can be extended to a more generalized reconfiguration problem for independent sets, called token addition and removal.
登录
查看更多内容
在无爪图中重新配置独立集
DOI：
10.1007/978-3-319-08404-6_8
发表时间：
2014
期刊：
ArXiv
影响因子：
--
作者：
P. Bonsma;M. Kaminski;Marcin Wrochna
通讯作者：
Marcin Wrochna
游戏、谜题和计算
DOI：
--
发表时间：
2009
期刊：
影响因子：
--
作者：
R. Hearn;E. Demaine
通讯作者：
E. Demaine
有限带宽和树深度的重新配置
DOI：
10.1016/j.jcss.2017.11.003
发表时间：
2014
期刊：
J. Comput. Syst. Sci.
影响因子：
--
作者：
Marcin Wrochna
通讯作者：
Marcin Wrochna
DOI：
10.1007/978-3-319-13524-3_21
发表时间：
2014
期刊：
--
影响因子：
--
作者：
A. E. Mouawad;N. Nishimura;Venkatesh Raman;Marcin Wrochna
通讯作者：
Marcin Wrochna
平面图上令牌跳跃的固定参数可处理性
DOI：
10.1007/978-3-319-13075-0_17
发表时间：
2014
期刊：
Lecture Notes in Computer Science
影响因子：
--
作者：
Takehiro Ito;Marcin Kaminski;Hirotaka Ono
通讯作者：
Hirotaka Ono