On The Complexity of Distance-$d$ Independent Set Reconfiguration

Abstract

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 general graphs, perfect graphs, planar graphs of maximum degeree three and bounded bandwidth can be extended for $d geq 3$.