Information Technology Reference
In-Depth Information
Problem 2.4
(
Graph rigidity problem
) Given an input graph
X
via its adjacency
matrix, check whether the graph is rigid.
Clearly, an oracle for the automorphism problem, or by Mathon's result [
Mat79
],
the graph isomorphism problem, is sufficient to decide the rigidity of a graph. How-
ever, the other direction is open.
Open problem 2.5
Is the graph rigidity problem polynomial-time equivalent to the
graph isomorphism problem.
An important variant of graph isomorphism is the isomorphism of coloured
graphs. For this article, a
c
-
colouring
of a graph
X
, where
c
a positive integer, is
a map from the vertex set
V
(
X
)
to the set of integers 1
,...,
c
.Givena
c
-colouring
ψ
,the
i
th
colour class
is subset
ψ
−
1
of
a graph
X
and colouring
ψ
. We often suppress the colouring
ψ
when it is understood
from the context and just denote the coloured graph by
X
.Giventwo
c
-coloured
graphs
(
i
)
of
V
(
X
)
.A
coloured graph
is a tuple
(
X
, ψ)
, an isomorphism
f
between the underlying graphs
X
and
Y
is a
coloured graph isomorphism
if it respects the vertex colours, i.e. for any ver-
tex
(
X
, ψ)
and
(
Y
, ϕ)
. An automorphism of a coloured graph is analogously
defined. Clearly coloured graph isomorphism generalises graph isomorphism as we
can assume an ordinary graph as 1-coloured graph. In the other direction, coloured
graph isomorphism polynomial-time Turing reduces to the graph isomorphism
problem. The key idea is the following
gadget construction
. For a coloured graph
X
,
we construct a new graph
v
of
X
,
ψ(v)
=
ϕ(
f
(v))
X
by first adding, for each colour class
i
, a long path
L
i
+
+
(say of length
n
1). We then connect all the vertices of the colour class
i
to one
of the end points of
L
i
. Given coloured graphs
X
and
Y
, any isomorphism between
the modified graphs
X
and
Y
forces the vertices in a given colour class of
X
to be
mapped to the vertices of the same colour class in
Y
due to the graph gadgets
L
i
.
Therefore, the coloured graphs
X
and
Y
are isomorphic if and only if the modified
graphs
X
and
Y
are isomorphic. The rigidity problem and the automorphism problem
generalise naturally to coloured graphs as well.
The graph isomorphism problem and the automorphism problem can be defined
for directed graphs as well. It turns out that these variants are polynomial-time Tur-
ing reducible to the undirected case. Therefore, in this article, we mostly concentrate
on undirected graph isomorphism. Nonetheless, from the perspective of the isomor-
phism problem, there is an important subclass of directed graphs called
tournaments
that we define below.
i
Definition 2.6
A directed graph
X
is a
tournament
if for every two distinct vertices
u
and
v
, exactly one of the directed edge
(
u
,v)
or
(v,
u
)
exists in
E
(
X
)
.
The automorphism group of a tournament cannot have a 2-cycle (why?), and
hence has to be of odd order. This forces it to be
solvable
by Feit-Thompson
theorem [
FT63
]. This property has been exploited by Babai and Luks [
BL83
]to
give significantly efficient algorithms for tournament isomorphism.
