Newsgroups: comp.theory
From: Hoey@AIC.NRL.Navy.Mil (Dan Hoey)
Date: 1997/03/31
Subject: Re: Help on Garey and Johnson

Jeff <maddalon@erols.com> writes (with my emendations):

> Could some kind person explain PERMUTATION GENERATION (MS6) to me?
> Instance: Permutation f of the integers {1,2,...,N} and a sequence
> S1, S2, ...,Sp of subsets of {1,2,...,N}
> Question: Can f be expressed as composition f=f1 . f2 . ... . fp,
> where for each i, 1<=i<=p, fi is a permutation of {1,2,...,N} that
> leaves all elements in {1,2,...,N} - Si fixed?
> ... Unfortunately the "reference" G&J refer to is unpublished....

The terminology has been adequately explained, but there is still the
problem of the reference.  I've been thinking about it off and on for
the past week.  Garey and Johnson claim a transformation from X3C, but
I have not been able to make that work.  However, I have come up with
a transformation from THREE-DIMENSIONAL MATCHING (3DM).

Suppose we have an instance of 3DM: a subset M of W x X x Y,
where W, X, Y are disjoint sets of size q.  The question is whether
there exists a subset M' of M, |M'|=q, such that no two elements of M'
agree in any coordinate.  I will assume that we have a nontrivial
instance, in the sense that every element of W, X, and Y appears as a
coordinate in M.

I will construct an instance of MS6 based on the permutations of the
integers {1,2,...,3m}, where |M|=m.  These integers should be
considered to stand for the coordinates as they appear in M.  In
particular, the integers A={1,2,...m} will stand for the
W-coordinates, the integers B={m+1,m+2,...,2m} will stand for the
X-coordinates, and the integers C={2m+1,2m+2,...,3m} will stand for
the Y-coordinates.  I will use the map
  E: (A union B union C) -> (W union X union Y)
to refer to this correspondence.  Note that E is just a concrete way
of expressing the given set M={(E(1),E(m+1),E(2m+1)),
(E(2),E(m+2),E(2m+2)), ..., (E(m),E(2m),E(3m))}.

The sequence of restriction sets S1,S2,...,Sp will consist of three
contiguous subsequences,

  SS1 = S1, S2, ..., S_3q;
  SS2 = S_3q+1, S_3q+2, ..., S_3q+2m;  and
  SS3 = S_3q+2m+1, S_3q+2m+2, S_3q+2m+3.

While I will temporarily put off their precise definition, I promise
that each subset in SS1 and SS3 will be a either a subset of A, a
subset of B, or a subset of C, so the corresponding permutations will
maintain the segregation of the permuted integers into A, B, and C.
The only mixing between the three sets will occur in the permutations
corresponding to SS2, in a construction that forms the tricky part of
the transformation.  The subsets in SS2 are defined as follows:

     S_3q+1 = {m+1,2m+1},   S_3q+2 = {1,m+1},
     S_3q+3 = {m+2,2m+2},   S_3q+4 = {2,m+2},
     S_3q+5 = {m+3,2m+3},   S_3q+6 = {3,m+3}, ...,
  S_3q+2m-1 = {2m, 3m},    S_3q+2m = {m,2m},

It is apparent that any interaction between permutations in SS2 will
occur between two adjacent subsets S_3q+2k-1, S_3q+2k.  Furthermore,
since these subsets are 2-sets, each permutation corresponding to them
will be either the identity or a transposition.  Thus there are only
four possible permutations induced on {k,m+k,m+2k} by the permutations
corresponding to SS2:

    i)       I      .      I       =         I,
   ii)       I      .   (k,m+k)    =       (k,m+k),
  iii)   (m+k,2m+k) .      I       =     (m+k,2m+k), and
   iv)   (m+k,2m+k) .   (k,m+k)    =   (k,m+k,2m+k)

The target permutation f will be chosen such that no integer in B is
mapped to A (prohibiting case ii) and no integer in C is mapped to B
(prohibiting case iii).  Therefore the only possible choices of
permutations on S_3q+2k-1, S_3q+2k will compose either to the identity
or to a three-cycle (k,m+k,2m+k).

The rest of the transformation is straightforward.  The subsets SS1
are simply the inverse images under E.  That is, for each value z in
W union X union Y, there is a set E^-1(z) in SS1 consisting of those
integers that correspond to the appearance of z as an index in M.  The
three subsets SS3 are just A, B, and C.  To define the target
permutation f, let us divide the set A = A1 union A2.  The set A1 will
consist of one representative from each inverse image of E^-1(W), so
that |A1|=q and E:A1->W is surjective (onto).  Similarly B1 is a set
of representatives of E^-1(X) and C1 is a set of representatives of
E^-1(Y), with A2=A\A1, B2=B\B1 and C2=C\C1.  Then we define f such that

  f : A1 -> {m+1,  m+2,  ..., m+q},
      B1 -> {2m+1, 2m+2, ..., 2m+q},
      C1 -> {1,    2,    ..., q},

      A2 -> {q+1,    q+2,    ..., m},
      B2 -> {m+q+1,  m+q+2,  ..., 2m},
      C2 -> {2m+q+1, 2m+q+2, ..., 3m}.

To see that this transformation from 3DM to MS6 is faithful, suppose
that the given instance of 3DM has a solution.  Then the solution to
MS6 is found by using permutations on subsets in SS1 to move the
elements of A1, B1, and C1 to the 3q integers corresponding to indices
in the triples of M'.  Those integers are mapped in 3-cycles by
permutations on subsets in SS2, while the other integers are held
fixed.  Finally, permutations on subsets in SS3 are used to move the
images of A1, B1, and C1 to the initial part of A, B, and C.
Conversely, is not hard to see that this is the only way that one
element each of A1, B1, and C1 could be mapped into B, C, and A,
respectively, as required by the target permutation f.  QED.

Dan Hoey                                posted and e-mailed
Hoey@AIC.NRL.Navy.Mil