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

June 03, 2014Independent Set Reconfiguration in Cographs
Room: HalB 2FPaul Bonsma

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.

This result is one of the first to demonstrate how dynamic programming can be used to solve (PSPACE-hard) reconfiguration problems for restricted graph classes. The talk will start with an overview of many recent results on similar reconfiguration problems.