E-resources
PDF-
Kamiński, Marcin; Medvedev, Paul; Milanič, Martin
Theoretical computer science, 06/2012, Volume: 439Journal Article
We study problems of reconfigurability of independent sets in graphs. We consider three different models (token jumping, token sliding, and token addition and removal) and analyze relationships between them. We prove that independent set reconfigurability in perfect graphs (under any of the three models) generalizes the shortest path reconfigurability problem in general graphs and is therefore PSPACE-complete. On the positive side, we give polynomial results for even-hole-free graphs and P4-free graphs.
