# Is Optimal Swap Sorting NP-Hard?

Given an array of integers with duplicates, find the minimum number of swaps to sort the array. According to this question, the problem is NP-Complete but the reference given proves NP-Completeness for a more general case where the target array is unrestricted. Is there a reduction from the unrestricted case to the sorting case?

• May be I’m missing something, but it seems to me that the reference does prove NP-completeness of the sorting problem. In the paper, NP-hardness comes from a reduction from the maxDCD problem. Now, in the reduction of maxDCD to the interchange distance problem in Lemma 1, you can freely choose the order in which you enumerate the edges. If you enumerate the edges so that they are sorted according to the source vertex, the string $y$ will be sorted. Feb 5 at 11:06
• @EmilJeřábek Oh, I see! I think you are right, the authors mention that the order can be arbitrary so the edges can be sorted by their origin vertex and then transformed into the two strings where one string is sorted. Do you mind posting it as an answer? Feb 7 at 0:16

Their proof of NP-hardness of the interchange distance problem goes by reduction from the maxDCD problem. Now, the reduction in Lemma 1 allows one to choose freely the ordering of the edges (as mentioned there); if you choose it such that the edges are sorted according to their source vertices, the target string $$y$$ is sorted.