8
$\begingroup$

While reading the post, Probability of generating a desired permutation by random swaps, by Aaronson, and to continue my program I started in this post, How hard is reconstructing a permutation from its differences sequence?, I got interested in this problem of sorting:

Input: a sequence $A$ of $2N$ positive integers (may contain repeated integers).

Question: Is it possible to sort sequence $A$ using $N$ transpositions?

Each transposition swaps two non-adjacent elements $a_i$ and $a_j$ in $A$ (two elements are not adjacent if $|i−j|>1$). This means that the two elements can not be adjacent in $A$. I guess the problem should be $NP$-complete.

Is this problem $NP$-complete? Is there an obvious Karp reduction from the $NP$-hard problem in Aaronson's post?

This was posted on TCS SE and had a bounty but without an answer.

P.S. This problem has a nice geometric interpretation: It is equivalent to deciding the existence of a path of length at most N between two points on a special 2N-Permutahedron.

Special permutahedron means that two nodes are connected by an edge if and only if the corresponding permutations are separated by one non-adjacent transposition.

Permutahedron of order 4

$\endgroup$
5
  • 1
    $\begingroup$ I don't understand what you mean by swapping non-adjacent entries. Usually we consider either all transpositions, or adjacent transpositions. Paths on the permutohedron definitely correspond to sequences of adjacent transpositions. Also, there is a very simple polynomial time algorithm to decide if you can get from one permutation to another using a given number of adjacent transpositions (because of the definition of "length" of an element of the symmetric group in terms of inversions) $\endgroup$ Apr 2, 2018 at 23:45
  • $\begingroup$ @SamHopkins It means swapping integers in two non-adjacent positions inside the array. Special permutahedron means that two nodes are connected by an edge if and only if the corresponding permutations are separated by one non-adjacent transposition. $\endgroup$ Apr 3, 2018 at 3:40
  • 1
    $\begingroup$ So the picture is not supposed to depict this “special permutohedron”? E.g., there is an edge between 1234 and 1324 in the picture, but that’s an adjacent swap, right? $\endgroup$ Apr 3, 2018 at 11:44
  • $\begingroup$ @SamHopkins Yes, that's right. $\endgroup$ Apr 3, 2018 at 12:14
  • $\begingroup$ What is the Coxeter structure if you take all non-adjacent transpositions as generators and only the $(g_i g_j)^{m_{ij}}$ type relations. This doesn't quotient by nearly enough to get to $S_N$, but it is computationally nice. $\endgroup$
    – AHusain
    Sep 2, 2018 at 6:49

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.