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
Search WWH ::




Custom Search