# Jun 03, 2014: Paul Bonsma: Independent Set Reconfiguration in Cographs

June 03, 2014 | Independent Set Reconfiguration in Cographs |

Room: HalB 2F | Paul Bonsma |

12:40-13:30 | We study the following independent set reconfiguration problem: given two independent sets A and B (of equal size) of a graph G, does there exist a sequence of independent sets of G that starts with A, ends with B, such that every independent set in the sequence can be obtained from the previous one by replacing one vertex? This problem is PSPACE-hard in general. In this talk we will show that it can be solved in polynomial time if G is a cograph. |