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

Theorem 5.4 (Arvind and Kurur) The graph isomorphism problem is in SPP.

While computing the lexicographically least element in a coset has an efficient
algorithm, consider the following generalisation to a double coset.

Problem 5.5 ( Lex-least in a double coset ) Given the generating sets of permutation
groups G and H on a totally ordered set ˇ and an arbitrary permutation x on ˇ ,

compute the lexicographically least element in GxH .

The problem of computing the lex-least element in a double coset is intimately
connected to the problem of graph canonisation which we define below.

Definition 5.6 ( Canonical forms for graphs ) Consider the class G(ˇ) of all graphs

on the vertex set ˇ . A function CF on G(ˇ) is a canonical form if it satisfies the

following properties:

1. For every graph X in is isomorphic to X .

2. If X and Y are two isomorphic graphs then CF

G(ˇ) , CF ( X )

( X ) is the same as CF ( Y ) .

In other words, a canonical form CF picks a unique representative from each
isomorphism class of graphs on

. Clearly graph isomorphism is solvable given
a canonisation procedure. Therefore, one way of attacking the graph isomorphism
problem is to give fast canonisation procedure. For many classes of graphs, Babai
and Luks [ BL83 ] gave an efficient canonisation procedure which is also currently the

ˇ

best general purpose algorithms. In particular, they were able to give an O n c log n
for tournaments. This canonisation procedure makes use of the fact that tournaments
have a solvable automorphism group. They also show how Luks' polynomial-time
algorithm for bounded valance [ Luk82 ] can be modified and extended to a canoni-
sation algorithm with essentially the same running time.
As opposed to computing the lexicographically least element in a coset, computing
it in a double coset is known to be NP-hard [ Luk93 , Theorem 5.1] even when one of
the group is solvable. However, in many contexts, particularly in relation with graph
isomorphism and canonisation, we have some freedom to choose the underlying
ordering of the set

so as to make it possible to apply
the divide and conquer technique similar to that of the colour preserving subgroup
problem that we saw in Sect. 11.4 . Indeed this is the case provided the reordering is
“compatible” with the divide and conquer structure of the group G . First, we need to
generalise the lexicographically least element as follows: Consider an ordering

ˇ . Can we reorder the set ˇ

< on

ˇ .Let be a G -stable set.We consider the restriction of the order < on the set .This

gives a partial order on elements of permutations, we say that g < h if for the least δ

h . Under this restricted ordering there
will be multiple lexicographically minimal elements. We now describe how to build
a new ordering

on which g and h differ, we have δ g < δ in

under which it is feasible to compute the lexicographically
least element of the double coset GxH .

⃐ on ˇ

Ordering the orbit Fix an ordering between the G -orbits by picking say the least
element in each of them. If

ˇ 1 and ˇ 2 are two orbits such that ˇ 1 <ˇ 2 in the