Summary: We study the following independent set reconfiguration problem: given two independent sets \(I\) and \(J\) of a graph \(G\), both of size at least \(k\), is it possible to transform \(I\) into \(J\) by adding and removing vertices one-by-one, while maintaining an independent set of size at least \(k\) throughout? This problem is known to be PSPACE-hard in general. For the case that \(G\) is a cograph on \(n\) vertices, we show that it can be solved in polynomial time. More generally, we show that for a graph class \(\mathcal {G}\) that includes all chordal and claw-free graphs, the problem can be solved in polynomial time for graphs that can be obtained from a collection of graphs from \(\mathcal {G}\) using disjoint union and complete join operations.
For the entire collection see [Zbl 1318.68028].