Independent set reconfiguration in H-free graphs
<|reference_start|>Independent set reconfiguration in H-free graphs: Given a graph $G$ and two independent sets of $G$, the independent set reconfiguration problem asks whether one independent set can be transformed into the other by moving a single vertex at a time, such that at each intermediate step we have an independent set of $G$. We study the complexity of this problem for $H$-free graphs under the token sliding and token jumping rule. Our contribution is twofold. First, we prove a reconfiguration analogue of Alekseev's theorem, showing that the problem is PSPACE-complete unless $H$ is a path or a subdivision of the claw. We then show that under the token sliding rule, the problem admits a polynomial-time algorithm if the input graph is fork-free.<|reference_end|>
@article{bartier2024independent,
    title={Independent set reconfiguration in H-free graphs},
    author={Valentin Bartier, Nicolas Bousquet and Moritz M"uhlenthaler},
    journal={arXiv preprint arXiv:2402.03063},
    year={2024},
    archivePrefix={arXiv},
    eprint={2402.03063},
    primaryClass={cs.DM cs.DS}
}