Permutation Groups and the Graph Isomorphism Problem - Perspectives in Computational Complexity - page 187

of m many copies of the symmetric groups S d − 1 for some positive integer m .The
quotient group G i + 1 / K i + 1 is the group H i + 1 , which itself is a subgroup G i , a group

in the class d − 1 : Consider any composition

series of G i + 1 which passes through the normal subgroup K i + 1 . The composition
factors are either composition factors of H i or that K i + 1 .
Having computed G i the algorithm computes G i + 1 by computing (1) a generating
set for the kernel K i + 1 and (2) a set of elements of G i + 1 whose restriction to G i
generates H i . It is this inductive step that requires the solution of colour preserving
subgroup problem and luckily the input group ( G i in our case) turns out to be in the
class

d − 1 . This is possible only if G i + 1 is in

d and hence solvable by the algorithm in Lemma 11.4.5. Thus, we have the
following theorem.

Theorem 4.6 (Luks) Consider the family G d of graphs whose vertices are of degree

bounded by d. There is a n O ( d ) algorithm to decide isomorphism of graphs in G d .

The current fastest algorithm for graph isomorphism [ ZKT85 ] is based on a
valence reduction step together with the application of the above theorem of Luks
for bounded valence graphs. Therefore, any improvement on the bounded valence
case will improve the state of the art for the general graph isomorphism problem.

11.5 Lexicographically Least Permutations

We now mention some results that make use of the ordering of permutations induced
by the ordering on the domain ˇ . First, note that a total ordering on the set ˇ gives

a total ordering on Sym (ˇ) : for distinct permutations g and h , g < h if at the first

h . We call
this ordering the lexicographic ordering on the permutations. Under this ordering
the lexicographically least permutation is the identity permutation. The first problem
that we study is the problem of computing the lexicographically least element in a
coset.

where they differ, we have α g < α (in the ordering on ˇ ) element α in ˇ

Problem 5.1 ( lexicographically least in a coset ) Given a permutation group G on
ˇ as a set of generators and an arbitrary permutation x on ˇ , compute the lexico-

graphically least element in the coset Gx .

Clearly if x is in G then the coset is the group G itself and the lexicographically
least element of the coset is the identity element. We now sketch a polynomial-time
algorithm for this problem.
Let α be the least element of ˇ . The set of images of α under permutations in the

Gx G x which can be computed easily once the

coset Gx is given by the set α = (α )

G of α is computed. Clearly, the lexicographically least element of Gx should
map α to the least element β of α

orbit α

Gx .We can also compute, using the transitive closure
algorithm for orbits, an element x 1 in the coset Gx such that α

x 1

= β . Therefore,
the lexicographically least element of Gx is also the lexicographically least element