The Complexity of Independent Set Reconfiguration on Bipartite Graphs
The Complexity of Independent Set Reconfiguration on Bipartite Graphs
复制标题
DOI：
10.1145/3280825
复制
发表时间：
2019-01-01
影响因子：
1.3
通讯作者：
Mouawad, Amer E.
中科院分区：
文献类型：
--
作者：
Lokshtanov, Daniel;Mouawad, Amer E.
我们解决了所有三个常用的重新配置模型下的二分图上的独立集重新配置问题的复杂性。我们表明，令牌跳跃或令牌添加/删除模型下，该问题是NP-完全的。对于令牌滑动模型，我们证明了问题仍然是PSPACE完全的。
We settle the complexity of the INDEPENDENT SET RECONFIGURATION problem on bipartite graphs under all three commonly studied reconfiguration models. We show that under the token jumping or token addition/removal model, the problem is N P-complete. For the token sliding model, we show that the problem remains PSPACE-complete.