Information Technology Reference
In-Depth Information
11.3 Basic Polynomial-Time Algorithms
In this section, we mention some well-known polynomial-time algorithms for per-
mutation group problems. The very first polynomial-time algorithm is the algo-
rithm to compute the orbits of a permutation group. Let S be a generating set of the
permutation group G then define a relation α S β if there exists a g in S such that
α g
s
gives us all the G -orbits. We can thus compute the orbits efficiently by computing
reachability.
Lemma 3.1 There is a polynomial-time algorithm, which given a generating set S
of a permutation group G on
= β . It is easy to see that the symmetric, transitive closure of the relation
G .
Many permutation group algorithms follows the general scheme of first reducing the
problem to the transitive case by finding all the orbits of the group using the above
lemma, and then restricting the group to the orbit. This is followed by a divide can
conquer that is done on the blocks of the transitive action of the group. Thus, finding
the blocks of a transitive permutation group is a crucial step in various algorithms.
Let G be a transitive permutation group over
ˇ
and an α ˇ
, computes the orbit α
ˇ
. Fix any two elements α and β in
G .Let
ˇ
ʲ
be the smallest G -block containing both α and β then Sim's observed [ Sim67 ] that
vertices in any connected component C of the graph X α,β
and consider the graph X α,β whose vertices are
ˇ
and edges are
{ α, β }
is a G -block in the block
{ ʲ g | g
}
ʲ
system
. By running this algorithm on all pairs one
can compute the set of minimal (as well as maximal) blocks of G -blocks.
Lemma 3.2 There is a polynomial-time algorithm that takes as input the generating
set of a transitive permutation group G on
G
associated with
and decides whether G is primitive or
not. If the input group G is not primitive, then it computes a minimal (or maximal)
G-block system.
We already argued that a generating set of a group is a natural way to present a
permutation group. A strong generating set is a special generating set of a permutation
group that makes many computational tasks easy. Consider a permutation group G on
the set
ˇ
and let G ( i ) denote the subgroup
ˇ
. Fix an ordering
{ α 1 , ··· , α n }
on the set
ˇ
of G that fixes the first i elements of
ˇ
, i.e. the subgroup of all elements g of G such
that α g j
G ( 0 ) ···
G ( n 1 ) =
1
of subgroups of G .Let C i be any set of permutations that has exactly one element
from each right coset of G ( i ) in G ( i 1 ) , i.e. C i is a right transversal of G ( i ) in G ( i 1 ) .
Given any permutation g in G , there is an unique element, say h 1 ,in C 1 which is
in the same right coset of G ( 1 ) as that of g . It is easy to see that g = g h 1 is in
G ( 1 ) . Continuing this argument with g and the group G ( 1 ) , it is easy to see that
any element g can be expressed as a product h 1 ...
= α j for all 1
j
i . Consider the tower G
=
C i . In fact, if the
transversals C i 's are fixed, the above product representation is unique. Thus,
h n 1 , h i
i C i
forms a generating set of G which we call the strong generating set of G .Many
computational tasks become trivial once the strong generating set is calculated. For
example, the uniqueness of the product representation of g shows that the order of
the group # G is the product of the sizes i # C i .
Search WWH ::




Custom Search