Information Technology Reference
In-Depth Information
Problem 6.1
(
Bounded colour class graph isomorphism
) Fix a constant
b
.Given
two coloured graph
X
and
Y
such that the number of vertices in any given colour
class is bounded by
b
decide whether the graphs are isomorphic.
We abbreviate this problemas BCGI
b
. This restricted graph isomorphismproblem
does have polynomial-time algorithm but what about fast parallel algorithms? Luks
[
Luk86
] answered this question affirmatively by giving a reduction to a restricted
point-wise stabiliser problem and solving it in NC. Further careful analysis by Arvind
et al. [
AKV05
] showed that the problem lies in the Mod
k
L hierarchy. Together with
the hardness for this class [
Tor04
], we have a fairly tight classification of this variant
of graph isomorphism.
We now explain the overall structure of the algorithm for BCGI
b
. Both Luks
[
Luk86
] and Arvind et al. [
AKV05
] reduce the bounded colour graph isomorphism
problem to a restricted version of point-wise stabiliser problemwhich we now define.
Problem 6.2
(
bounded orbit point-wise stabiliser problem
) Given as input a set
ˇ
,
a subset
such that the
G
-orbits are all
of cardinality bounded by a constant
c
. Compute generating set of the point-wise
stabiliser subgroup
G
of
ˇ
and a permutation group
G
on
ˇ
()
.
We abbreviate this problem as PWS
c
. As mentioned before, the above problem is
solvable in polynomial-time. However, in this context, we are interested in providing
a parallel algorithm. What needs to be exploited is that the
G
-orbits are bounded and
thus
G
is actually a subgroup of a product of small symmetric groups, the symmetric
groups on each of the
G
-orbits.
To see the connection of the PWS
c
and BCGI
b
isomorphism we consider the
equivalent automorphism problem which we denote by AUT
b
.
Lemma 6.3
(Luks)
The
AUT
b
problem logspace reduces to
PWS
2
b
2
problem.
Here is the sketch of this reduction. Let
X
be the coloured graph and let
C
1
,...,
C
m
denote the colour classes into which the vertex set
V
(
X
)
is partitioned. The automor-
=
i
Sym
phism group is a subgroup of the product group
G
(
C
i
)
. We expressed
the automorphism group Aut
(
X
)
as a point-wise stabiliser of
G
on its action on
a different set
ˇ
that we construct as follows: Define the set
C
i
,
j
to be the set of
unordered pairs
C
j
and let
E
i
,
j
be the subset of edges
of
X
between the colour classes
C
i
and
C
j
. Define the set
{
u
,v
}
where
u
∗
C
i
and
v
∗
ˇ
i
,
j
to be the power set
of
C
i
,
j
then the edge sets
E
i
,
j
are actually
points
or element of
ˇ
i
,
j
. Consider the
natural action of
G
on the union
ˇ
=
i
,
j
ˇ
i
,
j
and let
be the subset of all the
points E
i
,
j
of
ˇ
. It is easy to see that the point-wise stabiliser of
G
with respect to
the subset
. Notice that each of the set
ˇ
i
,
j
are
G
-stable and hence the orbits of
G
are at most of size 2
(
is actually the automorphism group Aut
(
X
)
)
.
Both Luks [
Luk86
] and Arvind et al. [
AKV05
] then solve the PWS
c
problem.
While the actual algorithms of Luks [
Luk86
] and Arvind et al. [
AKV05
] are fairly
technical, we attempt to explain the essence of the algorithm and the permutation
group theory involved in those results.
b
2