Complexity of independent set reconfigurability problems

• DOI: 10.1016/j.tcs.2012.03.004
• Publication Date: 2012-03-16T20:15:36Z
• Authors: Marcin Kamiński; Paul Medvedev; Martin Milanič
• Keywords: Reconfigurability

AbstractWe 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.