Consider a connected graph $G$ and two connected induced subgraphs $A=G[S_A]$ and $B=G[S_B]$ with $|S_A|=|S_B|=n$. The problem consists of transforming $A$ into $B$ (or $S_A$ into $S_B$) using a minimal amount of "steps".
A step transforms a vertex set $S_i$ into $S_{i+1}$ as follows:
- Remove a vertex from $S_i$ to obtain $\hat{S_i}$ without disconnecting $G[\hat{S_i}]$.
- Then, include a vertex of $G$ from the neighbourhood of $G[\hat{S_i}]$ (i.e. any vertex not in $\hat{S_i}$ that is adjacent to any vertex in $\hat{S_i}$) into $\hat{S_i}$ to obtain $S_{i+1}$.
In my specific form of the problem $S_A$ and $S_B$ always have at least one vertex in common, but that's just a special case.
Despite searching for related literature I have not been able to come up with anything close enough to be useful. I have found pebble motion problems which seem similar but aren't concerned with the labelled vertices staying connected (also not to be confused with graph pebbling).
Then there is the graph relabeling problem (Kantabutra has done a bunch of work on this) whose general definition appears to fit this problem, but all the work I could find is only concerned with the same "switching functions" as the pebble motion problems.
Finally some graph grammars seem related, but while I did find graph relabeling systems, I'm under the impression that those have a completely different set of goals.
I have established a few basic properties (such as symmetry when swapping $A$ and $B$ and trivial upper bounds on steps) but have been unable to answer two important questions:
Is this problem NP-hard?
Are there problem instances where any vertex is removed more than once (being readded in between) in all optimal solutions, or can every problem be solved using at most one addition and removal of each vertex? I have found an example where an optimal solution removed a vertex more than once, but there were other optimal solutions that did not.
If you know keywords or articles to look for I'd be grateful for those, as I seem to have exhausted the combinations of search terms I can think of.