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

= i G i where
G i is the action of G on the i th orbit. For each of the groups G i , compute a special
normal series G i

The group G in question can be seen as a product of groups G

N i , t and let N k denote the produce i

= N i , 0 ··· N i , k .The

algorithm does a divide and conquer to compute N k () going one level at a time.

The base case of this divide and conquer is when the group N i , s hits a socle. The
socle of a group G is the group generated by the set of all minimal normal subgroups
of G . The main group theoretic result that is used is the O'Nan-Scott theorem (See
the topic by Dixon and Mortimer [ DM91 ] for a proof of this result) on the structure
of the socle of a primitive permutation group and its point-wise stabiliser.
For the details of the algorithm, we refer the reader to the conference paper of
Arvind et al. [ AKV05 ]. A detailed version is available in the Ph.D thesis of Kurur
[ Kur06 , Chap. 5]

11.7 Representation of Groups on Graphs

In this section, we look at the group representability problem. This problem was
defined and studied by Dutta and Kurur [ DK09 ] to explore the connection between
graph isomorphismand permutation group algorithms froma representation theoretic
point of view. Representation theory is the study of homomorphisms from a group
to the group GL , the automorphisms of a vector space V . In the context of graph

isomorphism, we would like to understand homomorphisms between groups and
automorphisms of graphs.

( V )

Definition 7.1 A representation of a group Gona graph X is a homomorphism
from the group G to the automorphism group Aut ( X ) of the graph X .

There is always a trivial representation that sends all the elements of the group
to the identity automorphism. What we are interested in is a non-trivial homomor-
phisms. The main problem of interest in this section is the following [ DK09 ].

Problem 7.2 ( Group representability problem ) Given a group G and a graph X ,
decide whether G has a non-trivial representation on X .

The hardness of the problemdepends on how the group G is presented.We assume,
unless otherwise mentioned, that G is provided to the algorithm via a multiplication
table. Therefore, one can assume that the input size is # G

. In studying
its connection to graph isomorphism, we can restrict the problem in two ways: (1)
restrict the groups to come from a natural class like, for example, solvable or abelian
or (2) restrict the class of graphs to say planar graphs or trees.
The very first result that we have in this context is the following [ DK09 ].

+ # V ( X )

Lemma 7.3 (Dutta and Kurur) The graph isomorphism problem is log-space many-
one reducible to the abelian group representability problem.