Complexity of independent set reconfigurability problems
Complexity of independent set reconfigurability problems
复制标题
DOI：
10.1016/j.tcs.2012.03.004
复制
发表时间：
2012-06-29
影响因子：
1.1
通讯作者：
Milanic, Martin
中科院分区：
文献类型：
--
作者：
Kaminski, Marcin;Medvedev, Paul;Milanic, Martin
我们研究图中独立集的可重构性问题。我们考虑三种不同的模型（令牌跳跃、令牌滑动以及令牌添加和删除）并分析它们之间的关系。我们证明完美图中的独立集可重构性（在三个模型中的任何一个下）概括了一般图中的最短路径可重构性问题，因此是 PSPACE 完备的。从积极的一面来看，我们给出了无偶孔图和无 P-4 图的多项式结果。 (C) 2012 Elsevier B.V. 保留所有权利。
We study problems of reconfigurability of independent sets in graphs. We consider three different models (token jumping, token sliding, and token addition and removal) and analyze relationships between them. We prove that independent set reconfigurability in perfect graphs (under any of the three models) generalizes the shortest path reconfigurability problem in general graphs and is therefore PSPACE-complete. On the positive side, we give polynomial results for even-hole-free graphs and P-4-free graphs. (C) 2012 Elsevier B.V. All rights reserved.