



















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 $Ω(k^2\cdot n)$. As a counterpart to these results, we also establish that $\textsf{Independent Set Reconfiguration}$ is PSPACE-hard on incomparability graphs, of which interval graphs are a special case.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。