4
$\begingroup$

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?

$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$ Feb 5 at 11:06
  • $\begingroup$ @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? $\endgroup$ Feb 7 at 0:16

1 Answer 1

3
$\begingroup$

Even though the authors do not explicitly formulate it that way, the paper [1] (the reference mentioned in the OP) does actually prove the NP-completeness of bounding the minimal number of swaps needed to sort an array.

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.

[1] Amihood Amir, Tzvika Hartman, Oren Kapah, Avivit Levy, Ely Porat: On the Cost of Interchange Rearrangement in Strings, SIAM Journal on Computing 39 (2010), no. 4 (2010), pp. 1444–1461, doi 10.1137/080712969.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.