code and graph isomorphism

[Edwin Clark]

By code I mean binary linear code.

I would appreciate any information
concerning the difficulty of
determining when two codes are
isomorphic. I have a hunch that
it would be as difficult as graph
isomorphism.

Edwin Clark

--
====================================================
W. Edwin Clark, Department of Mathematics
University of South Florida, Tampa, FL 33620-5700
http://gauss.math.usf.edu:80/~eclark/

[Takunari Miyazaki]

Edwin Clark (ecl...@goedel.math.usf.edu) wrote:
: By code I mean binary linear code.

:
: I would appreciate any information
: concerning the difficulty of
: determining when two codes are
: isomorphic. I have a hunch that
: it would be as difficult as graph
: isomorphism.

Graph isomorphism is polynomial-time reducible to testing
isomorphism of binary linear codes.

This may be a well-known fact though I do not know of any reference
that explicitly states it in this form. However, the result is
essentially contained in a reduction due to E. M. Luks (cf. p. 170
in E. M. Luks, Permutation groups and polynomial-time computation,
Groups and Computation (L. Finkelstein and W. M. Kantor, eds.),
DIMACS Ser. Discrete Math. Theoret. Comput. Sci., vol. 11, AMS,
Providence, 1993).

Luks reduces graph isomorphism to finding normalizers in symmetric
groups. The permutation groups costructed in the reduction have
orbits of size 2, which can be viewed as vector spaces over Z_2
(binary linear codes). Their normalizers corresponds to the
automorphism groups of the codes. Thus, finding automorphism groups
of graphs is reduced to finding automorphism groups of codes. The
same construction gives a reduction of graph-isomorphism testing to
code-isomorphism testing.

Here is Luks' reduction phrased in terms of codes rather than
permutation groups:

Reduction:

Let X = (V, E) be a graph, where V = {1, 2, ..., n} and |E| = m.
We construct a linear code C as a subspace of (Z_2)^k, where k =
n^2 + m as follows. The coordinates of each vector are indexed by
(1,1) through (n,n) and then (1) through (m).

For each vertex v, let c_v be the element of (Z_2)^k that

(1) has 1's for (v,1) through (v,n)th coordinates,
(2) has 1's for each (e)th coordinate, where e is incident with v
in X, and
(3) has 0's elsewhere.

Let C be the linear code spanned by the c_v's for v in V. Observe
that

(a) the only non-identity vectors in C with less than 2n 1's are
the c_v's;
(b) for v,w in V, {v,w} is an edge iff c_v and c_w have a 1 in the
same coordinate, namely the ({v,w})th coordinate.

For another graph Y, perform the same construction to get its code
D. Isomorphism from X to Y induces an isomorphism from C to D,
and the converse holds as consequence of (a) and (b).

It is an open question whether there is a reverse reduction of code
isomorphism to graph isomorphism. This is also the case for a number
of problems similar tp code isomorphism (see Luks, ibid).

--
Takunari Miyazaki miya...@cs.uoregon.edu
Dept. of Computer and Information Science (541)346-1383 (Office)
Univ. of Oregon (541)346-4408 (Department)
Eugene, OR 97403-1202 (541)346-5373 (FAX)