<p>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.</p>
<p>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 <span class="math-container">$y$</span> is sorted.</p>
<p>[1] Amihood Amir, Tzvika Hartman, Oren Kapah, Avivit Levy, Ely Porat: <em>On the Cost of Interchange Rearrangement in Strings</em>, SIAM Journal on Computing 39 (2010), no. 4 (2010), pp. 1444–1461, doi <a href="https://doi.org/10.1137/080712969" rel="nofollow noreferrer">10.1137/080712969</a>.</p>

CC BY-SA 4.0
2024-02-07T08:39:55.013Z
2024-02-07T08:39:55.013Z
Emil Jeřábek
<p>Given an array of integers with duplicates, find the minimum number of swaps to sort the array. According to <a href="https://cs.stackexchange.com/questions/119293/minimum-number-of-swaps-in-sorting-sequence?rq=1">this question</a>, 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?</p>

CC BY-SA 4.0
2024-02-05T11:06:47.210Z
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.
Emil Jeřábek
CC BY-SA 4.0
2024-02-07T00:16:55.697Z
@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?
Daniel García
<np-hardness><co.combinatorics><optimization><reductions>
Is Optimal Swap Sorting NP-Hard?
Daniel García
# Is Optimal Swap Sorting NP-Hard?

(Asked by: username_0 on 2024-02-05)

Given an array of integers with duplicates, find the minimum number of swaps to sort the array. According to [this question](https://cs.stackexchange.com/questions/119293/minimum-number-of-swaps-in-sorting-sequence?rq=1), 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?

**Tags:** np-hardness, co.combinatorics, optimization, reductions

> **Comments:**
> **username_1**: 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.  
> **username_0**: @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?  

---

## 1 answers

### Answer by username_1 on 2024-02-07. Score: 3 | Accepted answer

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](https://doi.org/10.1137/080712969).


---

