How can I reduce a product of transpositions?

Question

I'm looking for an algorithm to solve the following task:

Input: a set $T$ of transpositions; a permutation $\pi$ expressed as a product of transpositions from $T$
Desired output: express $\pi$ as the shortest possible product of transpositions from $T$.

In other words, the output should be a list of transpositions $\tau_1,\dots,\tau_k$ such that $\pi = \tau_1 \circ \dots \circ \tau_k$, $\tau_1,\dots,\tau_k \in T$, and $k$ is as small as possible.

Is there an algorithm for this that will be efficient in practice?

For example, if I were given (2,3)(0,3)(0,3)(2,6)(2,3)(2,6)(0,3) = (0623), I could reduce it to (2,6)(2,3)(0,3) = (0623).

I have come up with a few methods, based on the following properties:

1. The product of identical transpositions cancel. For example, (1,2)(1,2)(2,3) = (2,3).
2. Any product of the form (x,y)(y,z)(x,y) is equal to (y,z)(x,y)(y,z).
3. Any transpositions which share no elements commute. That is, (u,v)(x,y)=(x,y)(u,v).

I have three methods, based on these three properties:

1. One simple method is simply finding instances of (1). In the first example, (0,3)(0,3) appears as a product, so I may remove those transpositions.

2. Another method is finding instances of (x,y)(y,z)(x,y)(y,z), since this is equal to (y,z)(x,y)(y,z)(y,z) = (y,z)(x,y).

3. A third method is to recognize if identical transpositions are separated by disjoint transpositions. For example, (0,3)(2,6)(0,3) = (0,3)(0,3)(2,6) = (2,6).

Are there any other methods I am missing here?

I will explain some of the context in which this problem appears. Consider a graph G with labelled vertices. On each vertex lies a pebble, $p_i$. A transposition in the given product corresponds to selecting an edge in G and swapping the pebbles that are incident to that edge.

Therefore, a product of transpositions corresponds to a process of exchanging pebbles of edges, and the end result is a permutation of the pebbles on G which is described by the permutation given by the product of transpositions.

Hence, this process of boiling down a product of transpositions is an attempt to reduce the number of exchanges needed to achieve any permutation of pebbles on a graph G.

Answer 1

I suspect your problem is NP-hard, but if you need to solve it in practice, I recommend using a SAT solver to help you.

Algorithms

I suggest you solve this using a SAT solver. The problem can be expressed in a fairly straightforward way as an instance of SAT, and then you can apply an off-the-shelf SAT solver.

Let's solve the following problem:

Input: $\ell \in \mathbb{N}$; a set $T$ of $m$ transpositions; a permutation $\pi$
Question: Does there exist a way to express $\pi$ as a product of $\le \ell$ transpositions?

We'll construct a way to solve this problem using SAT, then apply binary search over $\ell$ to find the optimal solution.

For simplicity, add the identity element to $T$. Then we can replace "$\le \ell$" with "exactly $\ell$". Now the question can be expressed in a rather straightforward way as a CNF formula.

In particular, introduce boolean unknowns $x_{i,\tau}$ (for each $i=1,2,\dots,\ell$ and each $\tau \in T$), with the intended meaning that $x_{i,\tau}=1$ means that $\tau$ is the $i$th transposition in the output sequence. Also, introduce boolean unknowns $y_{i,j,k}$, where $y_{i,j,k}=1$ is intended to mean that the first $i$ transpositions in the output sequence map $j$ to $k$. We add constraints:

• For each $i$, we require that exactly one of the $x_{i,\tau}$ is 1.

• We require that the product of the transpositions yields $\pi$, i.e., $y_{\ell,j,\pi(j)}=1$ for all $j$.

• We require that the $x$'s and $y$'s are consistent, e.g.,

  $$y_{i+1,j,k} = \bigvee_{\tau} y_{i,j,\tau^{-1}(k)} \land x_{i,\tau}.$$

• We require that $y_{0,j,j}=1$ for all $j$ and $y_{0,j,k}=0$ for $j \ne k$.

Now feed this to a SAT solver. This should be satisfiable if and only if there's a way to express $\pi$ as a product of $\ell$ transpositions from $T$.

Finally, use binary search on $\ell$, as mentioned above, to find the shortest possible way to express $\pi$ as a product of transpositions from $T$.

(There are many different ways to express this problem as SAT, and those choices might affect the performance of the SAT solver. So, if you need to solve this in practice, you might experiment with different ways of encoding the constraints into SAT.)

Hardness

I suspect your problem is NP-hard.

Researchers have studied a natural generalization of this problem where the set $T$ is allowed to contain arbitrary permutations, rather than just transpositions:

Inputs: $\ell \in \mathbb{N}$; a set $S$ of permutations; a permutation $\pi$
Question: Is there a way to express $\pi$ as a product of $\le \ell$ permutations from $S$?

This problem is NP-hard, as proven in the following paper:

The Minimum-Length Generator Sequence Problem is NP-Hard. S. Even, O. Goldreich. Journal of Algorithms, vol 2, pp.311-313, 1981.

This problem remains NP-hard even if \ell is specified in unary (i.e., there is not likely to be an algorithm that is polynomial in the length of the output). Subsequent work showed that the problem is PSPACE-complete if $\ell$ is specified in binary. That's not the same problem as yours, because you have the extra condition that $T$ contains only transpositions, but it is related.

A subsequent paper showed that if $T$ generates a transitive group, then the problem is NP-hard. In your case, this corresponds to the condition that the underlying graph be connected. I suspect you're dealing with a connected graph (otherwise you can trivially decompose into connected components and the complexity will depend on the size of the largest connected component). As a result, this appears to imply that your problem is NP-hard.

This hardness result is mentioned in Section 4 of the following paper:

The complexity of finding minimum-length generator sequences. Mark R. Jerrum. Theoretical Computer Science, vol 36, pp.265--289, 1985.

Assuming this is right, your options are to either look for a heuristic that will be always-efficient but not-always-optimal, or look for an always-optimal algorithm whose running time is not guaranteed to be always-efficient (e.g., by using a SAT solver).

Caveat: I don't have 100% confidence in my reasoning here. If I understand things correctly, it seems to contradict another claim in the same paper (namely, the one mentioned below about adjacent transpositions; those generate a transitive group, yet the corresponding problem isn't NP-hard). So I don't have full confidence that the problem is NP-hard. It's entirely possible I've misunderstood something or mis-applied the paper's results.

Other resources

Subsequent work has also shown that certain special cases can be solved in polynomial time, e.g., where $T$ contains all transpositions, or where $T$ contains all adjacent transpositions $(i,i+1)$, or where $T$ contains all cyclicly adjacent transpositions (i.e., all transpositions of the form $(i,i+1)$ together with $(n,1)$). However, that's probably not useful to you, as those correspond to rather trivial graphs (the complete graph, a line graph, or a $n$-cycle $C_n$).

You might also be interested in https://cstheory.stackexchange.com/q/21899/5038