\input{preamble}
\DeclareMathOperator{\Ker}{Ker}
\DeclareMathOperator{\Img}{Im}
\DeclareMathOperator{\Stab}{Stab}

\begin{document}
\lecture{Bounded degree and colour class GI}{Graph
Isomorphism}{Ramprasad Saptharishi}{Srikanth Srinivasan}

\section{Introduction}

We will give algorithms for two special cases of Graph Isomorphism,
namely when the input graphs are coloured so that each colour class is
of small size, and when the degree of each vertex is small. In
particular, when the colour class/degree is bounded, we will obtain
polynomial-time algorithms. 

\section{Bounded colour-class Graph Isomorphism}

The problem is the following: we are given two coloured graphs $G_1$
and $G_2$ such that each colour class is bounded by a constant $d$ in
size. We need to check if there is a colour preserving isomorphism
between the two. We solve an equivalent problem, the Graph
Automorphism problem, which is defined precisely below:

\begin{itemize} 
\item[] INPUT: Graph $(G = (V, E), f)$ where $f$ is a colouring
function that colours $V$ using a set $C$ of colours. For each colour
$c$, $|f^{-1}(\inbrace{c})|$ is bounded by a constant $d$.
\item[] PROBLEM: Compute a generating set for the set of all colour
preserving automorphisms of $G$.
\end{itemize}

That this problem is polynomial-time equivalent to the Graph
Isomorphism problem in the bounded colour setting can be proved
exactly as is it is in the general case (cf. Ramprasad's AlgComp
lecture notes, lecture 2).

Let us now look at the algorithm. Recall that the automorphism group
of a general graph consists of exactly those permutations of the set
$V$ of vertices that stabilize the edges of the graph (when the action of
these permutations on subsets of $V$ of size $2$ is considered).
Hence, if we consider the action of $S_{V}$ on $2^{\binom{V}{2}}$,
and consider the subgroup that stabilizes the set $E$ of edges, we
will get exactly the automorphism group of the graph. The obvious
drawback of this approach is that every element in this representation
of $S_{V}$ is exponential in size, and hence this gives us an
exponential time algorithm. But, in the bounded colour-class case,
this procedure can be slightly modified to give a polynomial-time
algorithm.

For any colour $i$, let $V_i$ denote those vertices in the input graph
that are coloured $i$, and $E_i$ denote edges in the input graph
between vertices that are coloured $i$. Also, for any distinct colours
$i, j$, let $E_{ij}$ denote those edges of the input graph between
vertices coloured $i$ and $j$.  Note that, in the bounded colour class
case, the elements of the automorphism group satisfy a much more
stringent condition: a permutation of $V$ is a colour-preserving
automorphism iff it stabilizes $V_i$, $E_i$, and $E_{ij}$ for all
colours $i$ and $j$. Hence, the subgroup we want is that subgroup of
$S = \otimes_{i}S_{V_i}$ that stabilizes the $E_i$s and the $E_{ij}$s.
But these are sets that are very small in size!  Every $E_i$, $E_{ij}$
is bounded in size by $d^2$. Hence, we can write down a generating set
for the action of the group $S$ on the set $\Omega' = \Union_{i}V_i
\union \Union_{i} 2^{\binom{V_i}{2}} \union \Union_{i\neq
j}2^{V_i\times V_j}$, a set of size at most $2^{d^2}n^2$. Now, we can
use standard techniques (Schreier's generators, etc.) to compute the
pointwise stabilizers of each of the $E_i$s and $E_{ij}$s in time
$\poly(2^{d^2}n^2)$. Clearly, when $d$ is a constant, this yields a
polynomial time algorithm.

\section{Bounded degree Graph Isomorphism}

Now, let us look at the Bounded degree Graph Isomorphism problem. The
problem $\GIso_d$ is defined as follows: we are given as input two graphs
$G_1$ and $G_2$ of maximum degree at most $d$, and we are required to
check if they are isomorphic. The problem is easily seen to be trivial
for the case when $d<3$, so let us consider the easiest non-trivial
case, i.e $d=3$. We will show that GI, in this case, reduces to the
Set-Stabilizer problem over a particularly simple kind of group,
namely a $2$-group. Since we can do this in polynomial time, we will
arrive at a polynomial time algorithm for $\GIso_3$. We will then
consider extensions to this for the $\GIso_d$ problem, where $d$ is
arbitrary. 

\subsection{$\GIso_3$}

We describe the algorithm for $\GIso_3$.

Let $G_1 = (V_1, E_1)$ and $G_2 = (V_2, E_2)$ be the input graphs.
Without loss of generality, we may assume that the two graphs are
connected (otherwise, we run the algorithm described below for all
pairs of connected components and count the number of components of
each isomorphism type -- this drives up the running time by some fixed
polynomial factor). For each $e_1 \in E_1$ and $e_2 \in E_2$, we
construct a graph $G_{e_1, e_2}$ as follows:

\begin{itemize}
\item Subdivide the edge $e_1$ into two by adding vertex $u$. Call this
new graph $G_1'$.
\item Subdivide $e_2$ by adding vertex $v$. Let this graph be $G_2'$.
\item Take the disjoint union of $G_1'$ and $G_2'$ and add an edge $e$
between the vertices $u$ and $v$.
\end{itemize}

Clearly, the graph $G_{e_1, e_2}$ is connected and the degree of each
of its vertices is bounded by $3$. We compute a generating set for the
set of all automorphisms of $G_{e_1,e_2}$ that fix the edge $e$ (but
may swap its endpoints). It is easy to see that, if we can do the
above, we can easily check if there is an isomorphism from $G_1$ to
$G_2$ that swaps the edges $e_1$ and $e_2$ (the connectedness of the
graphs is used here). Moreover, if we can do the above in time $t(n)$,
then we can solve $\GIso_3$ in time $O(t(n)\cdot \poly(n))$. From now
onwards, we concentrate on finding the generating set above. Let us
refer to the graph $G_{e_1, e_2}$ simply as $G$.

\begin{center}
\includegraphics[width=3.5in]{bGI_1.png}
\end{center}

For each $i \in \inbrace{0,\ldots,n}$, we define the graph $X_i$ to be
that subgraph of $G$ that is spanned by those edges that are at
distance at most $i$ from $e$. In particular, $X_0$ consists only of
the edge $\inbrace{u,v}$ and $X_n$ is the entire graph $G$
(connectedness!). Let $V_i$ denote the set of vertices that belong to
$X_{i+1}$ but not to $X_i$.  Note that this set of vertices is an
independent set in $X_{i+1}$; also note that any automorphism of $G$
must fix the set $V_i$ of vertices for each $i$.
Finally, let $A_i$ denote the set of automorphisms of $X_i$ that leave
$e$ fixed. We will compute the generating set of the $A_i$s in order. 

The generating set of $A_0$ is trivial to compute. Assume that
we have a generating set for $A_i$, where $i < n$. We want to compute
a generating set for $A_{i+1}$. Note that any automorphism in
$A_{i+1}$ must fix the set of vertices $X_j$, for any
$j< i$. Hence, the restriction of any map in $A_{i+1}$ to $V(X_i)$ is
an automorphism of $X_i$. Let $\varphi$ this natural restriction map
from $A_{i+1}$ to $A_i$. Clearly, $\varphi$ is a homomorphism. We will
compute a generating set for $A_{i+1}$ as follows:

\begin{itemize}
\item[(1)] Compute a generating set for $\Ker(\varphi)$.
\item[(2)] Compute a generating set for $\Img(\varphi)$.
\item[(3)] Compute the inverse images of each of the generators of
$\Img(\varphi)$ computed above. These form a set of coset
representatives of $\Ker(\varphi)$ in $A_{i+1}$. Hence, together with
the generating set for $\Ker(\varphi)$, we have a generating set for
all of $A_{i+1}$.
\item[(4)] Reduce the size of the generating set obtained above to
quadratic/linear size using standard filtering algorithms.
\end{itemize}

Let us see how (1) is accomplished. $\Ker(\varphi)$ consists exactly
of those automorphisms of $X_{i+1}$ that fix each vertex of $X_i$.
Consider any such automorphism $\pi$. Let $u$ be a vertex in
$X_{i+1}\setminus X_i$. Note that $\pi(u)$ can only be a vertex $v$
that has the \emph{same} neighbourhood set as $u$. Moreover, there is
at most one such $v\neq u$: this is because the degree of every vertex is at
most $3$ and thus each vertex in $X_i$ is adjacent to at most two
vertices in $V_i$. Let us call $u$ a \emph{twin} if
there exists such a vertex $v$, and a \emph{loner} if there is no such
vertex. Now it is easy to describe $\Ker(\varphi)$: every vertex in
$X_i$ is fixed, and so is every loner in $V_i$; every
pair of twins in $V_i$ may be fixed or swapped. Thus,
$\Ker(\varphi)$ is generated by all automorphisms of $X_{i+1}$ that
swap a single pair of twins and fix all the other vertices.

\begin{center}
\includegraphics[width=3.5in]{bGI_2.png}
\end{center}

The above reasoning gives us a little more. It tells us that every
$A_i$ is a $2$-group. This fact is easily proved by induction on $i$.
The case $i=0$ is trivial. To go from $i$ to $i+1$, note that
$\Img(\varphi)$ is a subgroup of a $2$-group and hence a $2$-group.
Also, $\Ker(\varphi)$ consists only of elements of order $2$ and
hence, by Cauchy's theorem, it is a $2$-group also. Thus, $A_{i+1}$ is
a $2$-group.

Now on to (2) and (3). Note that an element $\pi$ of $A_{i}$ belongs to
$\Img(\varphi)$ (i.e it is extendable to an automorphism of $X_{i+1}$)
iff it satisfies the following:

\begin{itemize}
\item It stabilizes the set of edges between vertices in $X_i$. (Note
that new edges may have been added between vertices in $X_i$ at this
stage.)
\item It maps the neighbourhood of every pair of twins to a
neighbourhood of a pair of twins, and the neighbourhood of every loner
to a loner.
\end{itemize}

Formally, let $U$ denote the class of subsets of $V(X_i)$ of size at
most $3$. Define the sets $U_1$, $U_2$, and $U_3$ as follows:
\[U_1 = \inbrace{\inbrace{w_1,w_2} \in U\ |\ (w_1,w_2) \in E(X_{i})}\]
\[U_2 = \inbrace{a \in U\ |\ a \text{ is the neighbourhood of a
loner}}\]
\[U_3 = \inbrace{a \in U\ |\ a \text{ is the neighbourhood of a pair of
twins}}\]

Hence, the elements of $A_{i}$ that are in $\Img(\varphi)$ are
exactly those that fix each of $U_1$, $U_2$, and $U_3$. Thus,
if we extend the action of $A_{i}$ to $U$ as well, we can find a
generating set of $\Img(\varphi)$ by computing the set-stabilizer of
$U_1$, $U_2$ and $U_3$. For now, we shall assume that this can be done
in polynomial time. 

Having done the above, we can easily find a preimage of each element
generating $\Img(\varphi)$. If $\pi \in \Img(\varphi)$, we can extend
$\pi$ to an element $\pi'$ of $A_{i+1}$ as follows: if $u$ in $V_i$ is
a loner, $\pi$ maps its neighbourhood to that of a loner, say $v$ --
we set $\pi'(u) = v$; similarly, if $u$ and $v$ are twins, then their
common neighbourhood is mapped to another neighbourhood of
twins, say $u'$ and $v'$ -- set $\pi'(u) = u'$ and $\pi'(v) = v$. It
is easily seen that $\pi'$ belongs to $A_{i+1}$. This completes (2)
and (3). Step (4) is standard. This completes the description of the
algorithm, modulo the assumption that the set-stabilizer for
$2$-groups can be computed in polynomial time.

\subsection{Extensions to $\GIso_d$}

Most of the above algorithm extends in a straightforward manner to the
general $d$-degree case. Once again, for each edge $e_1$ and $e_2$, we
construct the graph $G_{e_1,e_2}$, and compute a generating set for
the set of all automorphisms that fix the added edge $e$. We use all the
notation introduced above. 

As before, we are faced with the problem of computing a generating set
for $A_{i+1}$ given a generating set for $A_i$. We fix the restriction
map $\varphi: A_{i+1}\rightarrow A_i$. Let us follow the same template
that we used above.

We first classify the vertices in $V_i$ into $d$ types as follows: we
say that a vertex $v$ is of \emph{type $j$}
($j\in\inbrace{1,\ldots,d-1}$) if there are precisely $j-1$ other
vertices $v_1,\ldots,v_{j-1}\in V_i$ that have the same neighbourhood
set as $v$; we will refer to $v_1,\ldots,v_{j-1}$ as the
\emph{siblings} of $v$. The fact that any vertex has at most $d-2$
siblings follows from the degree restriction on the graph.

We now proceed with Step(1). Note that any element $\pi$ of
$\Ker(\varphi)$ can only map a vertex $v$ to one of its siblings;
moreover, restricted to a set of siblings, the mapping $\pi$ can be an
arbitrary permutation. Using this, one can easily construct a small
generating set for $\Ker(\varphi)$. This concludes Step (1).

We now need to construct a generating set for $\Img(\varphi)$. An
element $\pi$ of $A_i$ belongs to $A_{i+1}$ iff:

\begin{itemize}
\item It stabilizes the set of edges added between vertices in $X_i$.
\item For every $j\in\inbrace{1,\ldots,d-1}$, it maps the
neighbourhood of a set of siblings of type $j$ to another such
neighbourhood.
\end{itemize}

We formalize this identically to the way we did it above. Let $U$
denote the class of subsets of $V(X_i)$ of size at most $d$. Define the
sets $U_0, U_1,\ldots,U_{d-1}$ as follows:
\begin{eqnarray*}
& U_0 = \inbrace{\inbrace{w_1,w_2} \in U\ |\ (w_1,w_2) \in E(X_{i})}&\\
U_i =& \inbrace{a \in U\ |\ a \text{ is the neighbourhood of a
set of siblings of type $i$}}&\text{for $1\leq i \leq d-1$}
\end{eqnarray*}

Now, extend the action of the elements in $A_i$ to all the sets in
$U$. $\Img(\varphi)$ consists exactly of those elements of $A_i$ that
stabilize each of the $U_i$s defined above. Hence, the problem of
constructing a generating set for $\Img(\varphi)$ reduces to the set
stabilizer problem over $A_i$. Above, we noticed that all the $A_i$s
were $2$-groups and we claimed that the set stabilizer problem here
can be solved in polynomial time. In this case, we posit that we still
need to solve a simplified version of the general set stabilizer
problem, and that this can be done in polynomial time.

\newcommand{\Bd}{\mathcal{B}_d}
\begin{definition}
Given $d\in\N$, a finite group $G$ is said to belong to the class
$\Bd$ if all of its composition factors are (isomorphic to) subgroups
of $S_d$.  
\end{definition}

Note that the group $\Ker(\varphi)$ is a subgroup of a group of the
form $\otimes_{i=1}^{k}S_i$, where each $S_i$ is a permutation group
inside $S_d$. It is easy to check that $S_d\times S_d \times \cdots
\times S_d$ is in $\Bd$. We shall prove that the class $\Bd$ is closed
under subgroups, and hence that it contains $\Ker(\varphi)$.

\begin{claim}
\label{bd_claim}
For all $i\in\inbrace{1,\ldots,n}$, the group $A_i$ defined above
belongs to $\Bd$.
\end{claim}

\begin{claim}
\label{poly_claim}
The set stabilizer problem over groups in $\Bd$ can be solved in time
$n^{O(d)}$.
\end{claim}

We shall justify the above claims later. Assuming them, however, it is
easy to check that the remainder of the algorithm proceeds just as in
the $d=3$ case. We can pull back preimages of the generators of
$\Img(\varphi)$ easily, thus completing Step (3); and use any of the
standard algorithms we have already developed for Step (4). Hence, we
obtain an algorithm that runs in time $n^{O(d^2)}$ (the additional
factor of $d$ in the exponent comes from the fact that we need to run
the above mentioned set stabilizer algorithm on inputs of size
$n^{O(d)}$). 

\subsection{Proof of Claims}

We sketch the proofs of the claims mentioned above. We first need a
few facts about groups in $\Bd$.

\begin{claim}
\label{quo_claim}
Let $G \leq S_d$ and $N$ be a maximal normal subgroup of $G$. Then,
$G/N \leq S_d$ (up to isomorphism).
\end{claim}

\begin{proof}
Consider the following tower of subgroups:
\[N = G^{(d-1)}N \leq G^{(d-2)}N \leq \cdots \leq G^{(1)}N \leq GN = G\]
where $G^{(i)}$ denotes the subgroup of $G$ that stabilizes each of the
elements $1,\ldots,i$. Clearly, if $G=N$, the claim is trivially true.
Otherwise, there is some least $i$ such that $G^{(i+1)}N\subsetneq
G^{(i)}N$. It is easy to see that $[G^{(i)}N:G^{(i+1)}N]\leq
[G^{(i)}:G^{(i+1)}] \leq d$. Consider the action of $G = G^{(i)}N$ on the cosets
of $G^{(i+1)}N$ in $G^{(i)}N$. The action is clearly transitive (and
hence non-trivial). Also, the kernel of the action contains $N$. These
observations, together with the fact that $N$ is a maximal normal
subgroup, imply that the kernel of the action is $N$, and hence $G/N$
acts faithfully on the cosets. This implies that $G/N$ is a subgroup
of $S_d$.
\end{proof}

\begin{claim}
\label{subg_claim}
If $G$ is in $\Bd$, then so are all of its subgroups.
\end{claim}
\begin{proof}
Given any subgroup $H$ of $G$, consider the following tower of
subgroups:
\[H \intersection G_k \triangleleft H \intersection G_{k-1} \triangleleft \ldots
\triangleleft H \intersection G_{1} \triangleleft (H \intersection G) = H \]
where the $G_i$s form a composition series for $H$. It is an easy
exercise to check that $G_{i+1} \intersection H$ is indeed a normal
subgroup of $G_i \intersection H$, for all $i$. Hence, the above can
be extended (by adding subgroups of $H$ in between those shown above)
to a composition series for $H$.

Now, note that for any $i$, $(G_{i}\intersection
H)/(G_{i+1}\intersection H)$ is a subgroup of $G_i/G_{i+1}$ and hence,
is a subgroup of $S_d$. Now, if $K_1$ and $N$ are normal subgroups of
a group $K_2$, with $N$ being maximal normal, such that $K_1 \leq N$
and $K_1/K_2 \leq S_d$, then by Claim \ref{quo_claim}, $K_2/N\leq S_d$ as
well. By this fact, it is easy to infer that all composition factors
of $H$ are also in $S_d$.
\end{proof}

\begin{claim}
\label{subg_quo_claim}
Let $G$ be a finite group, and $N \triangleleft G$. A group $G$ is in
$\Bd$ iff $N, G/N$ are in $\Bd$.
\end{claim}
\begin{proof}
The proof is trivial, since the composition factors of $G$ are simply
the union of the composition factors of $N$ and $G/N$.
\end{proof}

\begin{proof}[Proof of Claim \ref{bd_claim}]
The proof is almost trivial from the above claims. We proceed by
induction on $i$. The case $i=0$ is immediate. Assume the statement
for $i$. By Claim \ref{subg_quo_claim}, to prove that $A_{i+1}$ is in
$\Bd$, it is sufficient to prove that both $\Ker(\varphi)$ and
$\Img(\varphi)$ are in $\Bd$. By Claim \ref{subg_claim} and the
induction hypothesis, $\Img(\varphi)$ is in $\Bd$. Also, as noted
above, $\Ker(\varphi)$ is a subgroup of a group of the form $S_d\times
S_d \times \cdots \times S_d$. The latter group can be checked to be
in $\Bd$. Hence, by Claim \ref{subg_claim}, the former is as well.
This concludes the proof of the claim.
\end{proof}

Hence, we have proved that the instance of Set Stabilizer we need to
solve is a special case of the general problem. We now sketch an
algorithm for this case. 

\subsubsection{Set Stabilizer for $\Bd$}

We need to solve the following problem: Given $G\leq \Sym(\Omega)$ in
$\Bd$ as a set of generators, and a set $\Delta\subseteq\Omega$, find
a set of generators for $\Stab_{\Delta}(G)$, the subgroup of $G$ that
stabilizes $\Delta$. 

First of all, note that we may assume that $G$ is transitive. Otherwise, if
$G$ has orbits $\Gamma_1,\ldots,\Gamma_k$, we can solve the problem by
finding the subgroup of $G$ that stabilizes
$\Delta\intersection\Gamma_i$ in each $\Gamma_i$.

We will now proceed by a `divide and conquer' strategy using the block
structure of $G$. What gives us hope of finding an efficient algorithm
is the following theorem that bounds the size of a primitive group in
$\Bd$, which we will use without proof:

\begin{theorem}[Babai, Cameron, and P\'alfy, 2002]
For any $d,n \in \N$, if $G\leq\Sym(\Omega)$ is a primitive group in
$\Bd$, and $|\Omega|=n$, then $|G|$ is bounded by $n^{cd}$, for some
absolute constant $c$.  
\end{theorem}

Hence, if $G$ was primitive, we have an easy algorithm: compute all of
$G$, and find all those elements that stabilize $\Delta$. However,
when $G$ is not primitive, we need to reduce to the primitive case.
For this, we will use the block structure of $G$, and some facts about
$\Bd$ that we proved above.

Assume $G$ is not primitive. Compute the structure tree of $G$ (cf.
Ramprasad's notes, Lecture 3). At the topmost level, $G$ acts
primitively on a set of blocks, say $\Omega_1,\ldots,\Omega_l$. Let
$H$ be the subgroup of $G$ that stabilizes each of the $\Omega_i$s.
Since, $H$ is the kernel of the action of $G$ on the blocks, $H
\triangleleft G$. Moreover, $G/H$ acts primitively on the set of
blocks. Hence, by the above theorem, $|G/H|\leq l^{cd}$. Let
$\tau_1,\ldots,\tau_m$ denote a set of coset representatives of $H$ in
$G$. Note that $\Stab_{\Delta}(G) = \Union_i \Stab_{\Delta}(H\tau_i)$.
However, this reduces the set stabilizer problem over groups to a set
stabilizer problem over cosets. Hence, we shall attempt to solve this
more general problem.

Assume we are given a group $G$, an element
$\sigma\in\Sym(\Omega)$, and a subset $\Delta$ of $\Omega$. We need to
find (a compact representation for) the set $\Stab_{\Delta}(G\sigma)$.
First of all, such a representation exists, which follows from the
following easy-to-prove claim:

\begin{claim}
\label{coset_claim_1}
$\Stab_{\Delta}(G\sigma)$ is either $\emptyset$ or a coset of
$\Stab_{\Delta}(G)$.
\end{claim}
\begin{proof}
Left to the reader.
\end{proof}

Also note that $\Stab_{\Delta}(G\sigma) = \Union_i
\Stab_{\Delta}(H\tau_i\sigma)$. Hence, we can now recurse using the
block structure as outlined above. The recursion produces, in all,
$n^{O(d)}$ many base cases. However, there is one catch: we can
no longer assume, as we did above, that $G$ is transitive. If $G$ does
have orbits $\Gamma_1,\ldots,\Gamma_k$, then we cannot compute
$\Stab_{\Delta\intersection\Gamma_1}(G\sigma)$ separately as $\sigma$
may not respect the orbit structure of $G$. Therefore, we need to
generalize the problem once more (for the final time!). Here is the
statement of the problem we will eventually give an algorithm for:

\begin{itemize} 
\item[] INPUT: Group $G \leq \Sym(\Omega)$ in $\Bd$ (as a generating
set), $\sigma\in\Sym(\Omega)$, $\Delta\subseteq\Omega$, and
$\Omega'\subseteq\Omega$ that is $G$-stable.
\item[] OUTPUT: The set of permutations $\pi$ in $G\sigma$ such that
$(\Delta\intersection\Omega')^{\pi}\subseteq\Delta$, and
$(\Omega'\setminus\Delta)^{\pi}\subseteq(\Omega\setminus\Delta)$ in a
compact form (i.e the output is of the form $H\sigma'$, for some
subgroup $H$ of $G$).
\end{itemize}

Let $\Stab_{\Delta}(\Omega',G\sigma)$ be the set of permutations
described above. The following claim is a generalization of Claim
\ref{coset_claim_1} we need:

\begin{claim}
\label{coset_claim_2}
$\Stab_{\Delta}(\Omega',G\sigma)$ is either $\emptyset$ or a coset of
$\Stab_{\Delta}(\Omega',G)$.
\end{claim}
\begin{proof}
Left to the reader.
\end{proof}

We now describe the algorithm. If $G$ is not transitive on $\Omega'$,
then $\Omega'$ is a union of more than one orbits of $G$. Assume
$\Omega' = \Gamma_1 \union\cdots\union \Gamma_k$. For simplicity, let
us consider the case $k=2$. In this case, we use the following:
$\Stab_{\Delta}(\Omega', G\sigma) =
\Stab_{\Delta}(\Omega_2,\Stab_{\Delta}(\Omega_1,G\sigma))$.
It is easy to extend this to arbitrary $k$. Hence, we have reduced the
intransitive case to the transitive case.

In case $G$ is not primitive on $\Omega'$, we consider the block
structure of $G$'s action on $\Omega'$, and recurse as described
above. If $G$ is primitive on $\Omega'$, then we know that $G$ is not
too large, and a simple enumeration of the elements of $G$ will
suffice.

It is a good exercise to prove that the running time of the above
algorithm is $n^{O(d)}$.

\subsection{Summary}

Let us summarize our approach to the $\GIso_d$ problem. Using the
input graphs, we constructed a graph (for every pair of edges) $G$
such that it is sufficient to construct a generating set for the set
of automorphisms of $G$ that fix a certain edge. We construct this set
by layering $G$ suitably, and noting that extending the automorphism
group from one layer to the next reduced to the Set Stabilizer problem
over a simpler kind of group. We then proceeded to give an algorithm
for the Set Stabilizer problem in this restricted case. The entire
algorithm runs in time $n^{O(d^2)}$. 

The proof above can be adapted to a slightly more general setting,
which we state below, since it will be useful later. The easy
extension is left to the reader. (The only part that needs to be
modified is showing that $\Ker(\varphi)$ above needs to be in $\Bd$.)

We consider coloured graphs $G=(V,E,f)$, where $f$ is a colouring
function that maps the vertices to colours from a set $C$.

\begin{definition}
A coloured graph is said to have \emph{Colour valence at most $d$} iff
for every $x\in V$, and every $c\in C$, either $|N(x)\intersection
f^{-1}(c)|\leq d$ or $|\overline{N(x)}\intersection f^{-1}(c)|\leq d$.
Here $N(x)$ denotes the neighbourhood of $x$.
\end{definition}

\begin{theorem}
\label{val_theorem}
For any $d\in \N$, there is an algorithm that, given any two coloured
graphs $G_1$ and $G_2$ of colour valence at most $d$, decides if there
is a colour-preserving isomorphism between the two graphs. The
running time of the algorithm is $n^{O(d^2)}$.
\end{theorem}

\end{document}