Information Technology Reference
In-Depth Information
ˇ
ˇ
Consider a permutation group
G
on
and let
be any subset of
.The
point-wise
()
stabiliser
of the set
, which we denote by
G
is the subgroup of all elements of
()
={
g
|
δ
g
=
δ,
δ
∗
}
G
that fix every element of
G
, i.e.
G
. It is easy to see that
finding the point-wise stabiliser of any subset of
ˇ
can be done in polynomial-time
by adapting the Schreier-Sims algorithm.
11.4 Divide and Conquer Algorithms for Permutation Groups
We now illustrate a general technique that is used in many permutation group algo-
rithms by giving an algorithm to find the setwise stabiliser for special groups.
Although superficially similar to point-wise stabiliser, computing the setwise sta-
biliser is a different ball game. It is at least as hard as graph isomorphism: For a
graph
X
, consider the group
G
ˇ
=
V
(
X
)
2
.The
=
Sym
(
V
(
X
))
actingontheset
automorphism group of the graph
X
is the set-wise stabiliser of the subset
E
(
X
)
of
ˇ
. The setwise stabiliser problem is a variant of a more general problem which we
define below.
Problem 4.1
(
Colour preserving subgroup
)Let
G
be a permutation group on
ˇ
k
i
1
. Compute the sub-
group of
G
that stabilises each of the colour class
C
i
, i.e. compute the subgroup
{
g
∗
which is partitioned into
k
-colour classes
C
={
C
i
}
=
C
i
G
|
=
C
i
}
.
The setwise stabiliser problem is the special case when the number of colours is
2. While we cannot expect a polynomial-time algorithm for this problem in general
without solving the graph isomorphism problem, for special groups, we can solve
the above in polynomial-time. For example, if we know that the input group
G
is
solvable then we have a polynomial-time algorithm. In fact, the polynomial-time
algorithm of Luks [
Luk82
] for trivalent graphs uses such a subroutine as the group
that occurs there is a 2-group and hence is solvable.
We now given a sketch of the algorithm, detail of which can be found in the paper
by Luks [
Luk82
]. To avoid notation clutter we fix an input group
G
and the colouring
C
of
ˇ
. We say that a permutation
g
preserves colours of all elements in the subset
,
α
and
α
g
are in the same colour class. Let
H
be a subgroup
ʲ
if for all
α
∗
ʲ
of
G
and
ʲ
an
H
-stable subset of
ˇ
. We denote CP
(
H
,ʲ)
to be the subset of
H
that preserves the colours of elements of
.For
the divide and conquer algorithm to work, we need to generalise the problem to
cosets of permutation groups: We need to compute CP
ʲ
. Our task is to compute CP
(
G
,ˇ)
(
H
g,ʲ)
for the coset
H
g
of
the subgroup
H
of
G
where the set
ʲ
is
H
-stable. Note that
ʲ
is not necessarily
stabilised by elements of
H
g
.
The set CP
has the following crucial properties which follows more or
less directly from the definitions.
(
H
g,ʲ)
Lemma 4.2
1.
The set
CP
(
H
,ʲ)
is a subgroup of H .
2.
The set
CP
(
H
g,ʲ)
is either empty or is a coset of the group
CP
(
H
,ʲ)
.
