Information Technology Reference
In-Depth Information
Fig. 11.1
Luks gadget for
bounded valence graphs
X
1
X
2
e
1
e
2
e
We now discuss a natural context where the colour stabiliser problem for groups
in the class
d
occurs. Consider the graphs of valence
d
, i.e. all vertices are of degree
less than or equal to
d
. Luks [
Luk82
] gives a polynomial-time algorithm for this class
of graphs by reducing it to the colour preserving subgroup problem where the input
group
G
is in the class
d
−
1
. We quickly give a sketch.
Fix the two input graphs
X
1
and
X
2
. We assume that the graphs are connected,
otherwise we run the algorithm for each pair of connected components. Furthermore,
we restrict our attention to checking whether
X
1
and
X
2
are isomorphic via an
isomorphism that maps a particular edge
e
1
of
X
1
to an edge
e
2
of
X
2
: We just need
to repeat the procedure for all such pairs of edges to know whether
X
1
and
X
2
are
isomorphic.
Consider the new graph which we denote by
Z
which is essentially the disjoint
union of the graph
X
1
and
X
2
with an additional edge
e
that connects the mid points
of
e
1
and
e
2
(see Fig.
11.1
). If
d
2 is the maximum degree of any vertex in the input
graph then
Z
also has degree bounded by
d
. Luks algorithm for bounded valence
computes the group subgroup Aut
>
that maps the auxiliary edge
e
to itself. It is clear that the input graphs
X
1
and
X
2
are isomorphic if and only if
there is at least one element in Aut
(
Z
)
e
of Aut
(
Z
)
)
e
(and therefore in any generator set) that flips
the edge
e
. The algorithm then proceeds to compute the group Aut
(
Z
)
e
. First the
graph
Z
is layered as follows: Let the
i
th layer of
Z
, denoted by
Z
i
, be the subgraph
which contains all the edges (as well as the end points) at a distance
i
from the
auxiliary edge
e
. In particular, the graph
Z
0
consists of just the edge
e
and its end
points. All automorphisms of
Z
that stabilises the edge
e
has to preserve this layered
structure. The group Aut
(
Z
(
Z
)
e
is then computed by inductively computing the groups
G
i
Z
i
)
e
.
Inductively, Luks proves that
G
i
's are in the class
=
Aut
(
d
−
1
as follows: Let
H
i
+
1
denote the subgroup of
G
i
that is obtained by restricting elements of
G
i
+
1
on
Z
i
and let
K
i
+
1
be the associated kernel, i.e. the subgroup of
G
i
+
1
that is trivial when
restricted to
Z
i
. For a fixed vertex
u
in layer
i
, i.e. in the graph
Z
i
\
Z
i
−
1
, is connected
to at most
d
1 and these vertices have to be mapped
within themselves by elements of
K
i
+
1
. Therefore,
K
i
+
1
is a subgroup of a product
−
1 vertices in the layer
i
+
