Reconfiguring Independent Sets on Interval Graphs

Abstract

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 $\Omega (k^2\cdot n)$. As a counterpart to these results, we also establish that $\text{Independent Set Reconfiguration}$ is PSPACE-hard on incomparability graphs, of which interval graphs are a special case.

12 pages, 5 figures