我们研究了在令牌滑动规则下的独立集重配置问题。设 $I$ 是简单无向图 $G$ 的一个独立集。假设 $I$ 的每个顶点上都有一个令牌。这些令牌可以通过沿 $G$ 的边滑动逐个移动，每次移动后，带有令牌的顶点始终形成 $G$ 的独立集。
我们要解决的问题是，是否可以通过一系列步骤将 $I$ 转换为 $I'$，每一步涉及用当前独立集中的一个顶点的邻居替换该顶点，从而获得另一个独立集。这个问题被称为判断一个图的独立集是否可以从另一个独立集“到达”，已知对于分裂图、平面图和树宽有限的图是 PSPACE-hard。
尽管如此，对于某些图类，如树、区间图、无爪图、二部排列图、块图和共图，已获得多项式时间算法。我们为 $P_4$-整洁图和 $(q,q-4)$-图提出了一种多项式时间算法，这两个图族是共图的推广。
博主点评： 本文在复杂的独立集重配置问题上取得了重要的进展，尤其是在特定图类上的多项式时间算法，为后续研究提供了新的思路和方法。