Graph canonization method that facilitates re-canonizing after vertex deletions?

Question

I'm trying to improve a graph algorithm that involves for a given graph to search through a large number of its induced subgraphs, generated by removing individual vertices. To reduce the size of this search space, I am considering to convert these induced subgraphs into their canonical forms in order to identify and remove what are essentially duplicate search nodes.

However, I know that in general, graph canonization can be computationally costly, so doing it from a cold start for every single encountered subgraph probably offsets any efficiency gains from bringing their total number down. I'm also aware that there are many different ways of canonizing graphs.

Therefore my question: Is there some method of graph canonization which - while it may be costly to compute for the initial graph - makes it somewhat easier to bring back a previously canonical graph from which a single vertex (and its incident edges) were removed back into its canonical form?

If this is not possible, could you provide some intuition as to why re-discovering the canonical form of a canonical graph from which just a single vertex has been removed must inevitably be in general just as hard as finding the initial canonical form in the first place?

Any suggestions or insight here is greatly appreciated, thanks in advance!

EDIT: Misha Lavrov has provided a great answer showing that in general, re-canonization after vertex removal must be GI-hard. This prompts the follow-up questions: Are there any graph canonization methods that will at least in the average case be somewhat less expensive to restore a canonical labeling after vertex removal from a canonical predecessor graph than others? I'm going to implement one anyways to try this, so I might as well take the most promising candidate to reduce average runtime by as much as possible.

Answer 1

Re-canonizing a graph after vertex deletions is going to be at least as hard, up to some polynomial-time steps, as isomorphism testing. (In other words, it is GI-complete.)

Here's why. Suppose we've got two $n$-vertex graphs $G$ and $H$ and we want to test if they are isomorphic. We'll assume that they both have minimum degree $3$; this should not make anything easier. (It might be unnecessary, but it makes me feel better about the reversibility of step 1.)

1. First, we subdivide both $G$ and $H$: replace each edge $e$ by a degree-$2$ vertex $v_e$ adjacent to both endpoints of $e$. The subdivisions $S(G)$ and $S(H)$ are isomorphic if and only if $G$ and $H$ are isomorphic.
2. Just as $G$ and $H$ can both be obtained from the complete graph $K_n$ by deleting edges, $S(G)$ and $S(H)$ can both be obtained from the subdivision $S(K_n)$ by deleting vertices. So, starting with a canonical labeling of $S(K_n)$, if we could easily recompute the canonical labeling after vertex deletion, we could do that repeatedly to get canonical labelings of $S(G)$ and $S(H)$.
3. At this point, comparing the canonical labelings tells us whether $S(G)$ and $S(H)$ are isomorphic, so it tells us whether $G$ and $H$ are isomorphic.

In the process, we had to compute the canonical labeling of $S(K_n)$, but this is presumably easy to do systematically for each $n$, no matter what kind of canonical labeling scheme we use, because $S(K_n)$ is not a complicated graph. Then, we had to perform the delete-a-vertex-and-infer-the-new-labeling step $O(n^2)$ times on graphs with $O(n^2)$ vertices.