Reconfiguration of Regular Induced Subgraphs

Understand

We study the problem of checking the existence of a step-by-step transformation of $d$-regular induced subgraphs in a graph, where $d \ge 0$ and each step in the transformation must follow a fixed reconfiguration rule.

• Our problem for $d=0$ is equivalent to \textsc{Independent Set Reconfiguration}, which is one of the most well-studied reconfiguration problems.
• In this paper, we systematically investigate the complexity of the problem, in particular, on chordal graphs and bipartite graphs.
• Our results give interesting contrasts to known ones for \textsc{Independent Set Reconfiguration}.