Reconfiguring Independent Sets in Cographs

Abstract

Two independent sets of a graph are adjacent if they differ on exactly one vertex (i.e. we can transform one into the other by adding or deleting a vertex). Let $k$ be an integer. We consider the reconfiguration graph $TA{R}_k(G)$ on the set of independent sets of size at least $k$ in a graph $G$, with the above notion of adjacency. Here we provide a cubic-time algorithm to decide whether $TA{R}_k(G)$ is connected when $G$ is a cograph, thus solving an open question of~[Bonsma 2014]. As a by-product, we also describe a linear-time algorithm which decides whether two elements of $TA{R}_k(G)$ are in the same connected component.

Cited by in corpus (1)

• Linear-Time Algorithm for Sliding Tokens on Trees