Information Technology Reference
In-Depth Information
There are efficient programmes and libraries (see NAUTY for instance) that can
solve large instances of graph isomorphism that arise in practice. However, there
are no known polynomial-time algorithm for the general case. In complexity the-
ory, ever since the notion of NP-completeness has been formalised, the graph iso-
morphism problem has had an important status as it is believed to be a natural
example of a problem of intermediate complexity [
GJ79
, Chap. 7], i.e. neither in
P nor NP-complete: It is known that the graph isomorphism problem is in the
complexity class co-AM [
BHZ87
], a randomised version of co-NP, and its NP
hardness will result in the collapse of the polynomial hierarchy [
BHZ87
,
Sch87
].
Furthermore, Köbler et al. [
KST92
] showed that graph isomorphism is low for the
counting class PP by showing its membership in LWPP. This was further improved
by Arvind and Kurur [
AK02
] to SPP. As a result graph isomorphism is in and
low for various counting complexity classes like classes like
P etc. Thus, under
reasonable complexity theoretic assumptions, graph isomorphism is
not
NP-hard.
Ladner [
Lad75
] proved the existence of an infinite hierarchy of problems of inter-
mediate complexity assuming that P is different from NP. The graph isomorphism
problem, for reasons stated above, is believed to be a natural example.
In this article, we study graph isomorphism and related problems. There is now
a vast literature on graph isomorphism and we really cannot do justice to the topic
in such a short article. For a detailed study of graph isomorphism, mainly from a
complexity theoretic view point, we refer the reader to the excellent topic by Köbler
et al. [
KST93
]. This paper concentrates on one of the aspects of the graph isomor-
phism problem, namely its intimate connection to permutation group algorithms.
Permutation groups arise in the study of graph isomorphism problem because of its
close relation to the graph automorphismproblem. For a graph
X
, the automorphisms,
i.e. isomorphisms from
X
to itself, forms a group under function composition. We
can identify this group as a subgroup of the set of all permutations of the vertex set
V
≥
. Automorphisms, thus are symmetries of the graph. The computational prob-
lem of computing a generating set of the automorphism group is equivalent to the
graph isomorphism problem [
Mat79
]. Most algorithms for graph isomorphism that
make use of permutation group theory makes use of this connection. Understanding
the automorphism group of a graph is also in tune with what is now a guiding prin-
ciple in much of modern mathematics: understanding objects by understanding their
symmetries.
(
X
)
11.2 Preliminaries
We briefly review the group theory required for this article mainly to fix notation and
convention. For details please refer any standard topic on group theory, for example,
Marshall Hall [
Hal59
]. The
trivial group
that contains only the identity is denoted
by 1. For a group
G
, we use the notation
H
H
) to denote that
H
is a
subgroup of
G
.The
right coset
of the subgroup
H
of
G
associated with an element
g
∗
G
(or
G
G
is the set
H
g
={
h
g
|
∗
}
h
H
. The set of all right cosets form a partition of
G
