Reconfiguring Independent Sets on Interval Graphs

We study reconfiguration of independent sets in interval graphs under the token sliding rule. We show that if two independent sets of size $k$ are reconfigurable in an $n$-vertex interval graph, then there is a reconfiguration sequence of length $\mathcal{O}(k\cdot n^2)$. We also provide a construction in which the shortest reconfiguration sequence is of length $\mathrm{\Omega }(k^2\cdot n)$. As a counterpart to these results, we also establish that $\mathsf{\text{Independent}}\mathsf{\text{Set}}\mathsf{\text{Reconfiguration}}$ is PSPACE-hard on incomparability graphs, of which interval graphs are a special case.