THE DISTANCE OF A PERMUTATION FROM A SUBGROUPOF Sn
RICHARD G.E. PINCHFor Bela Bollobas on his 60th birthdayAbstract. We show that the problem of computing the distance of a given
permutation from a subgroup H of Sn is in general NP-complete, even under
the restriction that H is elementary Abelian of exponent 2. The problem
is shown to be polynomial-time equivalent to a problem related to finding amaximal partition of the edges of an Eulerian directed graph into cycles andthis problem is in turn equivalent to the standard NP-complete problem ofBoolean satisfiability.

1. Introduction
We show that the problem of computing the distance of a given permutationfrom a subgroup H of Sn is in general NP-complete, even under the restriction that
H is elementary Abelian of exponent 2. The problem is polynomial-time equivalent
to finding a maximal partition of the edges of an Eulerian directed graph into cycles
and this is turn equivalent to the standard NP-complete problem 3-SAT.
2. Distance in the symmetric group
We define Cayley distance in a symmetric group as the minimum number oftranspositions which are needed to change one permutation to another by postmultiplicationd(ρ, π) = min {n | ρτ1 . . . τn = π,τi transpositions } .

It is well-known that Cayley distance is a metric on Sn and that it is homogeneous,that is, d(ρ, π) = d I, ρ−1 π . Further, the distance of a permutation π from theidentity in Sn is n minus the number of cycles in π.
If H is a subgroup of Sn , then we define the distance of a permutation π fromH asd(H, π) = min d(η, π).
η∈HWe refer to Critchlow [2] and Diaconis [3] for background and further materialon the uses of the Cayley and other metrics on Sn .
Problem 1 (Subgroup–Distance). Instance: Symmetric group Sn , element π ∈Sn , elements {h1 , . . . , hr } of Sn , integer K.
Question: Is there an element η ∈ H = hh1 , . . . , hr i such that d(η, π) ≤ K?
The natural measure of this problem is nr where r is the length of the listof generators. The following result shows that every subgroup of Sn has a set ofgenerators of length at most n2 and hence we are justified in taking n as the measureof the various problems derived from Subgroup–Distance.
Proposition 1. Every subgroup of Sn can be generated by at most n2 elements.
Date: 20 November 2005.
1991 Mathematics Subject Classification. Primary 20B40; Secondary 05C38, 20B35, 68Q25.
1

2

RICHARD G.E. PINCH

Proof. Let H be a subgroup of Sn . It is clear that H is generated by the unionof one Sylow subgroup for every prime p dividing the order #H. The order of aSylow p-subgroup of H is pb where pb divides #H and hence n!. It is well-knownn(e.g. Dickson [4] I, chap 9) that the power of p dividing n! is at most p−1, so b ≤ n.
But consideration of the composition factors shows that a p-group of order pb canbe generated by a set of at most b elements: hence any Sylow subgroup of H canbe generated by at most n elements. Further, the set of prime factors of the orderof H forms a subset of the set of prime factors of n!, that is, of the primes up ton, and there are at most n such primes. Hence H can be generated by a set of atmost n2 elements.
Although we do not need the stronger result, it can be shown that any subgroupof Sn can be generated by at most 3n − 2 elements.
We define a subset of Sn tobe involutions
 with disjoint
 support (IDS) to be set(rj ) (rj )(1) (1)(i) (i)of elements of the form γj = xj yj. . . xj yj
where the xj , yj are all
distinct. The subgroup generated by an IDS is clearly elementary Abelian withexponent 2. Define the width of an IDS to be the maximum number of 2-cycles
rj in the generators γj . The problem IDSw–Subgroup–Distance is the problem
Subgroup–Distance with the list of generators restricted to be an IDS of width
at most w.
Theorem 2. The problem IDS6–Subgroup–Distance is NP-complete.
The Theorem will follow from combining Theorem 3 and Theorem 7. We deduce immediately that the more general problem Subgroup–Distance is also NPcomplete.
By contrast, the problem of deciding whether the distance is zero, that is, testingfor membership of a subgroup of Sn , has a polynomial-time solution, an algorithm
first given by Sims [8] and shown to have a polynomial-time variant by Furst,Hopcroft and Luks [5]. See Babai, Luks and Seress [1] and Kantor and Luks [7] fora survey of related results.
3. Switching circuits
Let G = (V, E) be a directed graph with vertex set V and edge set E. (We allow
loops and multiple edges.) For each vertex v define e+ (v) to be the set of edges outof v and e− (v) the set of edges into v. The in-valency ∂− (v) = #e− (v) and the outvalency ∂+ (v) = #e+ (v). We define a switching circuit to be a directed graph G forwhich ∂+ (v) = ∂− (v) = ∂(v), say, and for which there is a labelling l± (v) of each sete± (v) with the integers from 1 to ∂(v). (The labels at each end of an edge are notrelated.) A routing ρ for a switching circuit is a choice of permutation ρ(v) ∈ S∂(v)
for each vertex v. Clearly there is a correspondence between routings for a switchingcircuit G and decompositions of the edge set of G into directed cycles. We definea polarisation T for a switching circuit G to be an equivalence relation on the setof vertices such that equivalent vertices have the same valency, and call (G, T ) apolarised switching circuit. We say that a routing ρ respects the polarisation T if
the permutations ρ(x) and ρ(y) are equal whenever x and y are equivalent vertices
under T . We shall sometimes refer to a switching circuit without a polarisation, orwith a polarisation for which all the classes are trivial, as unpolarised.
Problem 2 (Polarised–Switching–Circuit–Maximal–Routing). Instance: Polarised
switching circuit (G, T ), positive integer K.
Question: Is there a routing which respects T and has at least K cycles in theassociated edge-set decomposition?

THE DISTANCE OF A PERMUTATION FROM A SUBGROUP OF Sn

3We define the width of a polarisation to be the maximum number of vertices in an
equivalence class of T . The problem Widthw–Valencyv–Maximal–Routing is
the problem Polarised–Switching–Circuit–Maximal–Routing with the widthof T constrained to be at most w and the in- and out-valency of each vertex in V
constrained to be at most v.
Theorem 3. Problem Width6–Valency2–Maximal–Routing is NP-complete.
4. Proof of Theorem 3We shall show that the problem 3-SAT, [LO2] of Garey and Johnson [6], which
is known to be NP-complete, can be reduced to the problem Width6–Valency2–Maximal–Routing.
We define a polarised switching circuit (G, T ) to be Boolean (or binary) if everyvertex has in- and out-valency 1 or 2. To each class C of the polarisation T we associate a Boolean variable a(C). There is then a 1-1 correspondence between routingsρ which respect T and assignments of truth values to the variables a(C), C ∈ T byspecifying that a(C) is 0 (false) if and only if the permutation ρ(v) is the identity
in S2 for every v in C, and 1 (true) if and only if ρ(v) = (1 2).
We denote a vertex in a polarisation class associated with the Boolean variable
a as in Figure 1. Out convention for drawing the diagrams will be to assume theedges round each vertex labelled so that 1 is denoted by either “straight through”
or “turn right”.
1
2@
 @
R@
@a@@

@
2
R1@
R@
22I
@I@a
 @1
R1@

RIRRFigure 1. A vertex in a switching circuit associated with theBoolean variable a, and the routings with a = 1 and a = 0 respectively
We associate a vertex with the negated variable ā by exchanging the input labels
1 and 2.
Our proof will proceed by finding polarised switching circuits for which the number of maximal cycles in a routing is a Boolean function of the variables.
For a single Boolean variable a define I(a) to be the switching circuit in Figure
2.

@
I@a
 @
R@

Figure 2. The switching circuit I(a).

4

RICHARD G.E. PINCH

For a pair of Boolean variables (a, b) define the polarised switching circuit E(a, b)
as in Figure 3.

I
@@
I@@ba
@@ R@
R@

Figure 3. The switching circuit E(a, b).
Further define the polarised switching circuit F (a, b) as in Figure 4.
@
@

R@
R@ab


 @
 @
R
@
R
@
1
1@

@
R
@
R@ab



@
@
R@
R
@
-Figure 4. The switching circuit F (a, b).
Define G(a, b) to be the disjoint union of F (a, b) and E(ā, b).
Proposition 4.
(1) The number of cycles in a routing for I(a) is 2 if a = 1
and otherwise 1.
(2) The number of cycles in a routing for E(a, b) is 2 if a = b and otherwise 1.
(3) The number of cycles in a routing for F (a, b) is 2 if a 6= b, 3 if a = b = 1
and 1 if a = b = 0.
(4) The number of cycles in a routing for G(a, b) is 2 if a = b = 0 and 4otherwise.
Proof. In each case we simply enumerate the cases.
For a triple of Boolean variables (a, b, c) define the polarised switching circuit
A(a, b, c) as in Figure 5.
Proposition 5. The number of cycles in a routing for A(a, b, c) is 1 if a = b = c = 0
and 3 otherwise.
Proof. Again, in each case we simply enumerate the cases.
Theorem 6. There is a polynomial-time parsimonious transformation from theproblem 3-SAT to the problem Width6–Valency2–Maximal–Routing.
Proof. Suppose we have an instance of 3-SAT: that is, a Boolean formula Φ oflength l in variables xi which is a conjunct of k clauses each of which is a disjunctof at most three variables (possibly negated). We transform Φ into a formula Φ0in variables yij by replacing the j th occurence of variable xi by the variable yij andTHE DISTANCE OF A PERMUTATION FROM A SUBGROUP OF Sn

514

@@@
R R R abc


@
@
@
2
RRR
3


@@@
R R R abc
@@
@3RRR1
@@@R R R abc
@@@4
RRR5

@@@R R R abc

@
@
@
RR25
RFigure 5. The switching circuit A(a, b, c).


(r)
(r )
conjoining clauses yi1 ≡ yi2 ∧ . . . ∧ yi i−1 ≡ yi i where the variable xi occurs
ri times in Φ. Clearly Φ and Φ0 represent the same Boolean function and have thesame number of satisfying assignments. Every variable in Φ0 occurs at most threetimes, and at most once in a disjunct deriving from a clause in Φ. Let n be thetotal number of variables in Φ0 ; certainly n ≤ l.
We form a polarised switching circuit Ψ from Φ0 as follows. Take a circuit
B(x, y, z) for every clause in Φ0 of the form (x ∨ y ∨ z); take a circuit G(x, y) for
every clause in Φ0 of the form (x ∨ y); take a circuit I(x) for every clause in Φ0 ofthe form (x); take a circuit E(x, y) for every clause in Φ0 of the form (x ≡ y). Let
the number of circuits of types B, G, I and E taken to form Ψ be b, g, i, and e
respectively. Put M = 3b + 4g + 2i + 2e. The resulting polarised switching circuit
has n classes, and each class in the polarisation is involved in at most one circuit ofthe form B, G or I: hence each class contains at most 4 + 1 + 1 = 6 vertices and thenumber of vertices in Ψ is thus at most 6n. Furthermore, a routing for Ψ has M
cycles if and only if the corresponding assignment of Boolean values gives Φ0 , andhence Φ, the value 1; otherwise a routing has less than M cycles.
Since the problem 3-SAT is known to be NP-complete, we immediately deduce that the problem Width16–Valency2–Maximal–Routing is NP-complete
as well. This proves Theorem 3.
5. Switching circuits and IDS
In this section we obtain a polynomial-time equivalence between the problems
Widthw–Valency2–Maximal–Routing and IDSw–Subgroup–Distance.
Theorem 7. There is a polynomial-time parsimonious equivalence between problems Widthw–Valency2–Maximal–Routing and IDSw–Subgroup–Distance.
Proof. Suppose we have an instance of IDSw–Subgroup–Distance, that is, anelementπ of 
Sn together with an IDS on a set of t generators {γj } with γj =(1)

(1)

(r )

(r )

(i)

(i)

xj yj. . . xj j yj j , the xj , yj all distinct and all the rj ≤ w. We construct a polarised switching circuit on a graph, vertex set V = {P (1), . . . , P (n)} ∪{Q(1, 1), . . . , Q(t, rt )}. Each vertex P (k) will be of in-valence and out-valence 1;
each vertex Q(j, i) will be of in-valence and out-valence 2. For each j up to t
and i up to rj we take edges from P (xij ) and from P (yji ) to Q(j, i) labelled 1 and
2 respectively, and edges from Q(j, i) to P π xij and to P π yji again labelled 1 and 2 respectively. We define a polarisation T on V by taking t classes
Cj = {Q(j, i) | i = 1, . . . , rj }; clearly the width of T is at most w.

6RICHARD G.E. PINCH

Conversely, suppose we have an instance of Widthw–Valency2–Maximal–
Routing, that is, a directed graph (V, E) with every vertex v having in- and outvalency two, a labelling l± (v) : e± (v) → {1, 2} of edges into and out of each vertex
v, and an equivalence relation T on V with t classes each of size at most w. Putn = #E. We define a permutation π of E as follows. For an edge e into a vertex
v, let π(e) be the edge f out of v which has label l+ (v)(f ) equal to l− (v)(e). We
further define an IDS by writing
down a seto of generators {γj } as follows. Forneach class of vertices Cj = vij | i = 1, . . . , rj in the polarisation T , let γj be the
product of transpositions of the form fij gij where fij and gij are the edges outof vertex vij . Since each class in T has at most w elements, each generator γj iscomposed of at most w transpositions.
In each case there is a correspondence between routings ρ of the switching circuit
which respect the polarisation T and permutations of the form πη where η runs overthe elements of the subgroup H of Sn generated by the γj : in this correspondence thenumber of cycles in the routing ρ is equal to the number of cycles in the permutationπη. Hence π is within distance d of the group generated by the γj if and only ifthere is a routing ρ with at least n − d cycles.
References[1] L. Babai, E.M. Luks, and Seress Á., Fast management of permutation groups, Proc. 29th
annual symposium on foundation of computer science (1988), 272–282.
[2] D.E. Critchlow, Metric methods for analysing partially ranked data, Lecture notes in statistics,
vol. 34, Springer Verlag, Berlin, 1985.
[3] P. Diaconis, Group representations in probability and statistics, IMS lecture notes, vol. 11,
Institute of Mathematical Statistics, Hayward CA, 1988.
[4] Leonard E. Dickson, History of the theory of numbers, Chelsea, New York, 1971, original
publication Carnegie Institute, Washington, 1919–23.
[5] M.L. Furst, J. Hopcroft, and E.M. Luks, Polynomial time algorithms for permutation groups,Proc. 21st IEEE FOCS, 1980, pp. 36–41.
[6] M.R. Garey and G.S. Johnson, Computers and intractability: a guide to the theory of npcompleteness, W.H. Freeman, San Francisco, CA, 1979.
[7] W.M. Kantor and E.M. Luks, Computing in quotient groups, Proceedings 22nd annual ACM
symposium on theory of computing, ACM Press, 1990, pp. 524–534.
[8] C.C. Sims, Computational methods in the study of permutation groups, Computational problems in abstract algebra (Oxford) (J. Leech, ed.), Pergamon Press, 1970, pp. 169–184.
2 Eldon Road, Cheltenham, Glos GL52 6TU, U.K.
E-mail address: rgep@chalcedon.demon.co.uk