Information Technology Reference
In-Depth Information
ˇ
ʲ
Lemma 2.1
be a block. Let
N denote the subgroup of G that setwise stabilises all the elements in the
Let G be a transitive permutation group on
and let
ʲ
-block
B(ʲ)
={
ʲ
g
|
g
∗
system
G
}
. Then N is a normal subgroup of G and G
/
N acts as a
permutation on
ʲ
-block system
B(ʲ)
. In addition, if
ʲ
is a maximal G-block then
this action of the group G
/
N is primitive.
In algorithms that deal with permutation groups, we need a succinct way to encode
them which we now describe. Any permutation of
ˇ
can be presented by an array of
#
. A permutation
group is presented via a list of permutations that generate the group. It is a well-
known fact that any group
G
has a generating set of size less than
ˇ
elements and hence can be encoded as a string of size
O
(
n
lg
n
)
and hence
this presentation of permutation group is reasonable. Thus, we assume that the input
size, for an algorithm that takes a generating set
S
of a permutation group
G
on
ↆ
lg #
G
≤
ˇ
,
is #
S
. Similarly, an algorithm that is expected to produce a permutation group
as output, should output a generating set of size polynomial in #
+
#
ˇ
. For example, the
strong generating set that we describe in the next section, is of size at most #
ˇ
2
.
By a graph, we mean an undirected graph, i.e. a finite set of vertices and an edge
set which is a subset of unordered pairs of vertices. We use
V
ˇ
to
denote the set of vertices and the set of edges of a graph
X
, respectively. A bijection
f
from
V
(
X
)
and
E
(
X
)
(
X
)
to
V
(
Y
)
is an
isomorphism
if for every two vertices
u
and
v
of
X
,the
{
,v
}
{
(
),
(v)
}
unordered pair
is an edge of
Y
.An
automorphism
of a graph
X
is an isomorphism from the graph to itself. The set of
automorphism of a graph
X
, denoted by Aut
u
is an edge of
X
if and only if
f
u
f
(
X
)
, form a group under composition.
In fact, Aut
.
In the article, we assume that a graph of
n
vertices is encoded as an
n
2
-bit strings
that represent its
n
(
X
)
is a permutation group on
V
(
X
)
×
n
adjacency matrix. We now define the
graph isomorphism
problem
.
Problem 2.2
(
Graph isomorphsim problem
)The
graph isomorphism problem
(GI
for short) is defined as follows: Given two undirected graphs
X
and
Y
via their
adjacency matrix, decide whether they are isomorphic.
The counting version of the graph isomorphism problem, denoted by #GI, is the
problem of computing the number of isomorphism between the two input graphs
(0 when they are not isomorphic).
Graph isomorphism problem is closely related to the
automorphism problem
that
we define next.
Problem 2.3
(
Automorphism problem
)The
automorphism problem
(AUT for short)
is the problem of computing a strong generating set of the automorphism group
Aut
of an input graph
X
.
Mathon [
Mat79
] proved that the problems GI, #GI and AUT are all polynomial-
time Turing reducible to each other. Therefore, in the setting of permutation group
algorithms, it is often the automorphism problem that is attacked for solving graph
isomorphism.
A graph
X
is said to be
rigid
if it has no non-trivial automorphism, i.e. if Aut
(
X
)
(
X
)
is the trivial group. We now define the graph rigidity problem.
