Independent set reconfiguration in cographs. (English) Zbl 1417.05149
Kratsch, Dieter (ed.) et al., Graph-theoretic concepts in computer science. 40th international workshop, WG 2014, Nouan-le-Fuzelier, France, June 25–27, 2014. Revised selected papers. Cham: Springer. Lect. Notes Comput. Sci. 8747, 105-116 (2014).
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].
For the entire collection see [Zbl 1318.68028].
MSC:
05C69 | Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) |
05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |
68Q25 | Analysis of algorithms and problem complexity |
90C39 | Dynamic programming |