First of all, I wouldn't think of this as a "graph isomorphism algorithm" in the sense that it's something we practically use to test if two graphs are isomorphic. It's a theoretical tool explaining why two related computational problems are equivalent:
- The decision problem, "Are graphs $G$ and $H$ isomorphic?"
- The search problem, "Find an isomorphism between $G$ and $H$ or determine that there is no isomorphism."
Of course, an algorithm for the search problem would be good enough to solve the decision problem - and in practice, the algorithms we use solve the search problem. But in principle, you could imagine an algorithm which solves the decision problem non-constructively: it tells you whether $G$ and $H$ are isomorphic, but not how.
It turns out that, if this were the case, we could still use the non-constructive algorithm to find an algorithm for the search problem - it just takes a few more steps! And that's what we're doing here.
Here's a high-level overview of what this algorithm is doing:
Let vi (resp., ui) denote the ith vertex of G1 (resp., G2) Initialize φ = ∅ and J = [n] For i = 1 to n do: For j ∈ J do: Let φ' be φ with the pair (vi,uj) added If φ' extends to an isomorphism between G1 and G2 do: set φ = φ' set J = J \ {j} loop to the next value of i Output φ
In words: the final output $\phi$ (an isomorphism from $G_1$ to $G_2$) can be thought of as a list of all pairs $(v_1, \phi(v_1)), \dots, (v_n, \phi(v_n))$. We figure out what these pairs are, one at a time. To figure out what the pair $(v_i, \phi(v_i))$ should be, we try taking it to be $(v_i, u_j)$ for each unused vertex $u_j$ in $G_2$, and seeing if it works.
"Seeing if it works" - checking if $\phi$ extends to an isomorphism between $G_1$ and $G_2$ - is the hard part. It's answering a decision problem of "Is there an isomorphism from $G_1$ to $G_2$ that sends $v_1, \dots, v_i$ to $\phi'(v_1), \dots, \phi'(v_i)$?" If the answer is yes, then all the pairs in $\phi'$ so far are correct, and so we set $\phi = \phi'$ and continue.
But this decision problem is not the same decision problem as "Is there an isomorphism from $G_1$ to $G_2$?" that we're assuming we know how to solve. We'll show how to reduce this problem to the one we know, and that's where "rooting a tree" comes in...
To summarize, here is the task that remains before us. We are assuming that we have an algorithm for the decision problem, "Is there an isomorphism from $G_1$ to $G_2$?" (In computer science, we often call this hypothetical algorithm an oracle.) We want to use this oracle to solve the decision problem "Is there an isomorphism from $G_1$ to $G_2$ that sends $v_1, \dots, v_i$ to $\phi'(v_1), \dots, \phi'(v_i)$?"
To do this, we add some structure to $G_1$ and $G_2$ to force these pairings to exist. There are different ways to do it. The algorithm in the question does the following:
- In $G_1$, add $n$ new degree-$1$ vertices adjacent to $v_1$, $2n$ new degree-$1$ vertices adjacent to $v_2$, ..., $i \cdot n$ new degree-$1$ vertices adjacent to $v_i$.
- In $G_2$, add $n$ new degree-$1$ vertices adjacent to $\phi'(v_1)$, $2n$ new degree-$1$ vertices adjacent to $\phi'(v_2)$, ..., $i \cdot n$ new degree-$1$ vertices adjacent to $\phi'(v_i)$.
In the modified graphs, $v_i$ and $\phi'(v_i)$ are distinguished as the only vertices with at least $i \cdot n$ neighbors of degree $1$, so any possible isomorphism has to pair them. Then, $v_{i-1}$ and $\phi'(v_{i-1})$ are distinguished as the only other vertices with at least $(i-1) \cdot n$ neighbors of degree $1$, so any possible isomorphism has to pair them. Continuing to reason in such a way leads us to conclude that the only possible isomorphism between the modified graphs has to agree with $\phi'$.
So we can invoke our oracle on the modified graphs to solve the decision problem we need in the algorithm, and we have a complete solution.
(The pseudocode in the question differs slightly from what we're doing, but only in cosmetic ways: it maintains the modified graphs as $G_1'$ and $G_2'$ as it goes, rather than reconstruct them each time, and it doesn't specifically define $\phi'$, though the idea of $\phi'$ is behind graphs $G_1''$ and $G_2''$. The actual logic is the same, though.)
