论文标题
关于距离的复杂性 - $ d $独立设置重新配置
On the Complexity of Distance-$d$ Independent Set Reconfiguration
论文作者
论文摘要
对于固定的正整数$ d \ geq 2 $，距离$ d $独立集（d $ d $ is）是一个顶点子集，其在任何两个成员之间的距离至少为$ d $。想象一下，d $ d $的每个成员都有一个令牌。如果可以通过将一个令牌从一个顶点移动到其一个空置的相邻顶点之一，则在令牌滑动下（$ \ mathsf {ts} $）下的两个D $ D $ ISS（$ \ mathsf {ts} $）相邻。在令牌跳跃下（$ \ Mathsf {tj} $），目标顶点不需要与原始的顶点相邻。距离 - $ d $独立集重新配置（D $ d $ isr）问题下的$ \ mathsf {ts}/\ mathsf {tj} $询问是否存在相邻的d $ d $ ISS的相应序列，该序列将一个给定的d $ d $转换为另一个。 $ d = 2 $的问题，也称为独立集重新配置问题，在文献中已经得到了充分研究，并且已经知道了几个图类别的计算复杂性。在本文中，我们研究了$ \ mathsf {ts} $和$ \ mathsf {tj} $在不同图下的d $ d $ isr的计算复杂性。在和弦图上，我们表明$ \ mathsf {tj} $下的d $ d $ isr在$ \ mathtt {p} $中时，$ d $均匀而$ \ m athtt {pspace} $ - 当$ d $ d $奇怪时。在拆分图上，有一个有趣的复杂性二分法：d $ d $ isr is $ \ mathtt {pspace} $ - $ d = 2 $，但在$ \ nathtt {p} $中，$ d = 3 $ for $ \ mathsf {ts} $ for $ d = 3 $ for $ d = 3 $ $ \ mathtt {pspace} $ - 完成$ d = 3 $。此外，在完美的图表上，$ d = 2 $的某些众所周知的硬度结果和最高学位的平面图和有界带宽的平面图可以以$ d \ geq 3 $进行扩展。
For a fixed positive integer $d \geq 2$, a distance-$d$ independent set (D$d$IS) of a graph is a vertex subset whose distance between any two members is at least $d$. Imagine that there is a token placed on each member of a D$d$IS. Two D$d$ISs are adjacent under Token Sliding ($\mathsf{TS}$) if one can be obtained from the other by moving a token from one vertex to one of its unoccupied adjacent vertices. Under Token Jumping ($\mathsf{TJ}$), the target vertex needs not to be adjacent to the original one. The Distance-$d$ Independent Set Reconfiguration (D$d$ISR) problem under $\mathsf{TS}/\mathsf{TJ}$ asks if there is a corresponding sequence of adjacent D$d$ISs that transforms one given D$d$IS into another. The problem for $d = 2$, also known as the Independent Set Reconfiguration problem, has been well-studied in the literature and its computational complexity on several graph classes has been known. In this paper, we study the computational complexity of D$d$ISR on different graphs under $\mathsf{TS}$ and $\mathsf{TJ}$ for any fixed $d \geq 3$. On chordal graphs, we show that D$d$ISR under $\mathsf{TJ}$ is in $\mathtt{P}$ when $d$ is even and $\mathtt{PSPACE}$-complete when $d$ is odd. On split graphs, there is an interesting complexity dichotomy: D$d$ISR is $\mathtt{PSPACE}$-complete for $d = 2$ but in $\mathtt{P}$ for $d=3$ under $\mathsf{TS}$, while under $\mathsf{TJ}$ it is in $\mathtt{P}$ for $d = 2$ but $\mathtt{PSPACE}$-complete for $d = 3$. Additionally, certain well-known hardness results for $d = 2$ on perfect graphs and planar graphs of maximum degree three and bounded bandwidth can be extended for $d \geq 3$.
