<p>This problem is NP-complete. I will prove NP-hardness below</p>

<h2>Source Problem</h2>

<p>Colored Token Swapping on Cliques: </p>

<p>In the colored token swapping problem, we are given a graph with a colored token placed on each vertex. We are given the color of each token. Also, each vertex has a target color which is also given. A swap is an operation in which the tokens on two adjacent vertices switch places. We are given a number <span class="math-container">$k$</span> and asked whether a sequence of at most <span class="math-container">$k$</span> swaps can result in each vertex having a token of the target color for that vertex. </p>

<p>In the colored token swapping on cliques problem, the graph is a clique (and so a swap can occur between any two tokens). Also, we can assume without loss of generality that the target coloring is reasonable; that is, we assume that for each color, the number of tokens of that color equals the number of vertices with that color as the target color.</p>

<p>This problem is shown NP-hard in Lemma 18 of <a href="http://www.lamsade.dauphine.fr/~bonnet/publi/token-swapping.pdf" rel="noreferrer">http://www.lamsade.dauphine.fr/~bonnet/publi/token-swapping.pdf</a>.</p>

<h2>Reduction</h2>

<p>We are given a colored token swapping on cliques instance. In other words, we are given </p>

<ul>
<li><span class="math-container">$n$</span>, the size of the clique. WLOG we can assume that the vertices of the clique are <span class="math-container">$1, 2, \ldots, n$</span>. </li>
<li>A function <span class="math-container">$t$</span> assigning a target color to each vertex. Since there are at most <span class="math-container">$n$</span> colors, we will also number the colors <span class="math-container">$1, 2, \ldots, n$</span> (some colors may be left unused).</li>
<li>A function <span class="math-container">$s$</span> assigning a starting token color to each vertex.</li>
<li>A number <span class="math-container">$k$</span>.</li>
</ul>

<p>Since we can reorder the vertices without changing the problem, we can assume WLOG that in <span class="math-container">$t$</span>, all vertices with the same target color are numerically contiguous (if vertices <span class="math-container">$i$</span> and <span class="math-container">$j$</span> have the same target color then every vertex numerically between them also has that same target color). Furthermore, assume WLOG that the color values are chosen so that <span class="math-container">$t$</span> is increasing (which we can do since we can permute color names without changing the problem).</p>

<p>Now we will construct an instance of your problem (given a set of constraints, a sequence, and a value <span class="math-container">$k$</span>, can the sequence be reordered in at most <span class="math-container">$k$</span> swaps so that the result is a topological sort of the DAG implied by the constraints.)</p>

<p>The value of <span class="math-container">$k$</span> we will use for your problem will equal the value <span class="math-container">$k$</span> from the token swapping instance.</p>

<p>The sequence we will use for the instance of your problem is <span class="math-container">$[1, 2, \ldots, n]$</span>.</p>

<p>Next, construct a permutation <span class="math-container">$p$</span> on <span class="math-container">$\{1, 2, \ldots, n\}$</span> such that <span class="math-container">$t(x) = s(p(x))$</span>. Notice that this is just a matching between <span class="math-container">$\{1, \ldots, n\}$</span> and <span class="math-container">$\{1, \ldots, n\}$</span> such that <span class="math-container">$i$</span> can be matched to <span class="math-container">$j$</span> only if the target color at vertex <span class="math-container">$i$</span> matches the color of the token initially at <span class="math-container">$j$</span>.</p>

<p>Define <span class="math-container">$C_x$</span> to equal <span class="math-container">$\{p(i)~|~t(i) = x\}= p(\{i~|~t(i) = x\}) = p(t^{-1}(x))$</span>. Notice that <span class="math-container">$C_1, C_2, \ldots, C_n$</span> partition <span class="math-container">$\{1, \ldots, n\}$</span>. We add constraints so that if <span class="math-container">$i &lt; j$</span>, all the elements of <span class="math-container">$C_i$</span> must come before all the elements of <span class="math-container">$C_j$</span>. This set of constraints is satisfied if and only if the elements of <span class="math-container">$C_1$</span> in any order occur before the elements of <span class="math-container">$C_2$</span> in any order, which themselves occur before the elements of <span class="math-container">$C_3$</span> in any order, etc...</p>

<h2>Correctness</h2>

<p>There is a correspondence between a token swapping instance and the instance of your problem produced by this reduction. Assign each token a number from <span class="math-container">$1$</span> to <span class="math-container">$n$</span>. In particular, assign the token initially at vertex <span class="math-container">$i$</span> (according to <span class="math-container">$s$</span>) the value <span class="math-container">$i$</span>. </p>

<p>Now the correspondence is that at all times, token <span class="math-container">$i$</span> is at vertex <span class="math-container">$j$</span> if and only if the value <span class="math-container">$i$</span> is at position <span class="math-container">$j$</span> of the sequence.</p>

<p>Certainly this correspondence holds at the beginning: each vertex <span class="math-container">$i$</span> contains token <span class="math-container">$i$</span> and the initial sequence is <span class="math-container">$[1, 2, \ldots, n]$</span>, which if 1-indexed has value <span class="math-container">$i$</span> at position <span class="math-container">$i$</span>.</p>

<p>Under this correspondence, a swap in the token swapping instance corresponds to a swap in the sequence. If we have tokens <span class="math-container">$x_1$</span> and <span class="math-container">$x_2$</span> at vertices <span class="math-container">$y_1$</span> and <span class="math-container">$y_2$</span>, then swapping those two tokens results in <span class="math-container">$x_1$</span> at <span class="math-container">$y_2$</span> and <span class="math-container">$x_2$</span> at <span class="math-container">$y_1$</span>. Similarly, if we have values <span class="math-container">$x_1$</span> and <span class="math-container">$x_2$</span> at positions <span class="math-container">$y_1$</span> and <span class="math-container">$y_2$</span> of the sequence, then swapping those two values results in <span class="math-container">$x_1$</span> at position <span class="math-container">$y_2$</span> and <span class="math-container">$x_2$</span> at position <span class="math-container">$y_1$</span>. Clearly, if we correspond swaps in this way, the invariant given by the correspondence is maintained.</p>

<p>Finally, under this correspondence, a solved token swapping instance (each token at a vertex whose target color matches the token's color) corresponds to a sequence that satisfies all constraints. This is not obvious, so here's a proof:</p>

<p>A sequence satisfies all the constraints if and only if the elements are in the order of <span class="math-container">$C_1$</span> elements first, then <span class="math-container">$C_2$</span> elements, etc... But the number of <span class="math-container">$C_1$</span> elements is <span class="math-container">$|C_1| = |p(t^{-1}(1))| = |t^{-1}(1)|$</span>, which is the number of vertices with target color <span class="math-container">$1$</span>. Since <span class="math-container">$t$</span> is increasing, these are the lowest-indexed vertices. Notice that the elements of <span class="math-container">$C_1$</span> have the lowest-indexed positions. Thus, the indices of the positions of <span class="math-container">$C_1$</span> elements exactly correspond to the indices of vertices with target color <span class="math-container">$1$</span>. Next, <span class="math-container">$|C_2| = |t^{-1}(2)|$</span>, so the next <span class="math-container">$|C_2|$</span> lowest indices belong to the positions of elements of <span class="math-container">$C_2$</span> and to the vertices with target color <span class="math-container">$2$</span>. </p>

<p>We can continue applying the same logic. This shows that a sequence satisfies all the constraints if and only if for each <span class="math-container">$i$</span>, each element <span class="math-container">$x$</span> of <span class="math-container">$C_i$</span> has a position <span class="math-container">$y$</span> whose corresponding vertex has target color <span class="math-container">$i$</span>. Under the correspondence, element <span class="math-container">$x$</span> has position <span class="math-container">$y$</span> if and only if token <span class="math-container">$x$</span> is at vertex <span class="math-container">$y$</span>. This shows that a sequence satisfies all the constraints if and only if for each <span class="math-container">$i$</span>, for <span class="math-container">$x \in C_i$</span>, the vertex containing token <span class="math-container">$x$</span> has target color <span class="math-container">$i$</span>. Remember, however, that <span class="math-container">$C_i = p(t^{-1}(i))$</span> and therefore that <span class="math-container">$s(C_i) = s(p(t^{-1}(i)))$</span>. Then by the definition of <span class="math-container">$p$</span> (that <span class="math-container">$t(x) = s(p(x))$</span>), we have that <span class="math-container">$s(C_i) = t(t^{-1}(i) = i$</span>. Thus, for every element <span class="math-container">$x$</span> of <span class="math-container">$C_i$</span>, <span class="math-container">$s(x) = i$</span>. Substituting this fact, we see that a sequence satisfies all the constraints if and only if for each <span class="math-container">$i$</span>, for <span class="math-container">$x \in C_i$</span>, the vertex containing token <span class="math-container">$x$</span> has target color <span class="math-container">$s(x)$</span>. But token <span class="math-container">$x$</span> has color <span class="math-container">$s(x)$</span>, so a sequence satisfies all the constraints if and only if every token is at a vertex whose target color matches that token.</p>

<p>Thus we have shown that the correspondence holds: a swap corresponds to a swap, the initial situations correspond, and situations that match the "victory conditions" also correspond. Thus, since the target number of swaps <span class="math-container">$k$</span> is the same, the two instances are equivalent.</p>

CC BY-SA 4.0
2020-06-01T09:02:01.543Z
Thanks a lot!  Your answer is correct and elegant.
2016310588
CC BY-SA 4.0
2020-07-27T04:09:45.997Z
I am so sorry for the wrong problem statement.
2016310588
CC BY-SA 4.0
2020-07-27T04:12:41.297Z
What I am looking for is that the topological order that is the most similar to the originally given sequence. The most similar means that the least number of elements is moved
2016310588
CC BY-SA 4.0
2019-01-05T12:49:04.963Z
2019-01-05T12:49:04.963Z
Mikhail Rudoy
<p>For example, given the constraints {<span class="math-container">$a&lt;b,c&lt;d$</span>} and a sequence <span class="math-container">$[b,a,c,d]$</span>. we just need swap <span class="math-container">$a$</span> with <span class="math-container">$b$</span> to get an topological sort, I want to ask how to find the sort solutions with minimum swaps</p>

CC BY-SA 4.0
2018-11-29T15:32:15.867Z
For example, given the constraints {$a<b,c<d$} and a sequence $[b,a,c,d]$. we just need swap $a$ with $b$ to get an topological sort, I want to ask how to find the sort solutions with minimum swaps.
2016310588
CC BY-SA 4.0
2018-11-29T15:34:29.173Z
by the way, to swap $b$ with $c$ is also an solution with one swaps
2016310588
CC BY-SA 4.0
2018-11-29T15:41:16.483Z
the original problem is as follows. given an $DAG$ and its certain topological sorted sequence $L_n$. Now here comes an new $Node v'$ and somes edges between it and the existing nodes, I want to insert $v'$ to the sequence $L_n$ to get the sequence $L_{n+1}$ which is an topological sort of the new $DAG$, how to achieve that with minium node swaps
2016310588
<np-hardness><sorting><topological-sorting>
how to achieve a topological sort of an given sequence with minimum swaps
2016310588
# how to achieve a topological sort of an given sequence with minimum swaps

(Asked by: username_0 on 2018-11-29)

For example, given the constraints {$a} and a sequence $[b,a,c,d]$. we just need swap $a$ with $b$ to get an topological sort, I want to ask how to find the sort solutions with minimum swaps

**Tags:** np-hardness, sorting, topological-sorting
> **Comments:**
> **username_0**: For example, given the constraints {$a<b,c<d$} and a sequence $[b,a,c,d]$. we just need swap $a$ with $b$ to get an topological sort, I want to ask how to find the sort solutions with minimum swaps.  
> **username_0**: by the way, to swap $b$ with $c$ is also an solution with one swaps  
> **username_0**: the original problem is as follows. given an $DAG$ and its certain topological sorted sequence $L_n$. Now here comes an new $Node v'$ and somes edges between it and the existing nodes, I want to insert $v'$ to the sequence $L_n$ to get the sequence $L_{n+1}$ which is an topological sort of the new $DAG$, how to achieve that with minium node swaps  

---

## 1 answers

### Answer by username_1 on 2019-01-05. Score: 5 | Accepted answer

This problem is NP-complete. I will prove NP-hardness below

## Source Problem

Colored Token Swapping on Cliques:

In the colored token swapping problem, we are given a graph with a colored token placed on each vertex. We are given the color of each token. Also, each vertex has a target color which is also given. A swap is an operation in which the tokens on two adjacent vertices switch places. We are given a number $k$ and asked whether a sequence of at most $k$ swaps can result in each vertex having a token of the target color for that vertex.

In the colored token swapping on cliques problem, the graph is a clique (and so a swap can occur between any two tokens). Also, we can assume without loss of generality that the target coloring is reasonable; that is, we assume that for each color, the number of tokens of that color equals the number of vertices with that color as the target color.

This problem is shown NP-hard in Lemma 18 of <http://www.lamsade.dauphine.fr/~bonnet/publi/token-swapping.pdf>.

## Reduction

We are given a colored token swapping on cliques instance. In other words, we are given

* $n$, the size of the clique. WLOG we can assume that the vertices of the clique are $1, 2, \ldots, n$.
* A function $t$ assigning a target color to each vertex. Since there are at most $n$ colors, we will also number the colors $1, 2, \ldots, n$ (some colors may be left unused).
* A function $s$ assigning a starting token color to each vertex.
* A number $k$.

Since we can reorder the vertices without changing the problem, we can assume WLOG that in $t$, all vertices with the same target color are numerically contiguous (if vertices $i$ and $j$ have the same target color then every vertex numerically between them also has that same target color). Furthermore, assume WLOG that the color values are chosen so that $t$ is increasing (which we can do since we can permute color names without changing the problem).

Now we will construct an instance of your problem (given a set of constraints, a sequence, and a value $k$, can the sequence be reordered in at most $k$ swaps so that the result is a topological sort of the DAG implied by the constraints.)

The value of $k$ we will use for your problem will equal the value $k$ from the token swapping instance.

The sequence we will use for the instance of your problem is $[1, 2, \ldots, n]$.

Next, construct a permutation $p$ on $\{1, 2, \ldots, n\}$ such that $t(x) = s(p(x))$. Notice that this is just a matching between $\{1, \ldots, n\}$ and $\{1, \ldots, n\}$ such that $i$ can be matched to $j$ only if the target color at vertex $i$ matches the color of the token initially at $j$.

Define $C\_x$ to equal $\{p(i)~|~t(i) = x\}= p(\{i~|~t(i) = x\}) = p(t^{-1}(x))$. Notice that $C\_1, C\_2, \ldots, C\_n$ partition $\{1, \ldots, n\}$. We add constraints so that if $i < j$, all the elements of $C\_i$ must come before all the elements of $C\_j$. This set of constraints is satisfied if and only if the elements of $C\_1$ in any order occur before the elements of $C\_2$ in any order, which themselves occur before the elements of $C\_3$ in any order, etc...

## Correctness

There is a correspondence between a token swapping instance and the instance of your problem produced by this reduction. Assign each token a number from $1$ to $n$. In particular, assign the token initially at vertex $i$ (according to $s$) the value $i$.

Now the correspondence is that at all times, token $i$ is at vertex $j$ if and only if the value $i$ is at position $j$ of the sequence.

Certainly this correspondence holds at the beginning: each vertex $i$ contains token $i$ and the initial sequence is $[1, 2, \ldots, n]$, which if 1-indexed has value $i$ at position $i$.

Under this correspondence, a swap in the token swapping instance corresponds to a swap in the sequence. If we have tokens $x\_1$ and $x\_2$ at vertices $y\_1$ and $y\_2$, then swapping those two tokens results in $x\_1$ at $y\_2$ and $x\_2$ at $y\_1$. Similarly, if we have values $x\_1$ and $x\_2$ at positions $y\_1$ and $y\_2$ of the sequence, then swapping those two values results in $x\_1$ at position $y\_2$ and $x\_2$ at position $y\_1$. Clearly, if we correspond swaps in this way, the invariant given by the correspondence is maintained.

Finally, under this correspondence, a solved token swapping instance (each token at a vertex whose target color matches the token's color) corresponds to a sequence that satisfies all constraints. This is not obvious, so here's a proof:

A sequence satisfies all the constraints if and only if the elements are in the order of $C\_1$ elements first, then $C\_2$ elements, etc... But the number of $C\_1$ elements is $|C\_1| = |p(t^{-1}(1))| = |t^{-1}(1)|$, which is the number of vertices with target color $1$. Since $t$ is increasing, these are the lowest-indexed vertices. Notice that the elements of $C\_1$ have the lowest-indexed positions. Thus, the indices of the positions of $C\_1$ elements exactly correspond to the indices of vertices with target color $1$. Next, $|C\_2| = |t^{-1}(2)|$, so the next $|C\_2|$ lowest indices belong to the positions of elements of $C\_2$ and to the vertices with target color $2$.

We can continue applying the same logic. This shows that a sequence satisfies all the constraints if and only if for each $i$, each element $x$ of $C\_i$ has a position $y$ whose corresponding vertex has target color $i$. Under the correspondence, element $x$ has position $y$ if and only if token $x$ is at vertex $y$. This shows that a sequence satisfies all the constraints if and only if for each $i$, for $x \in C\_i$, the vertex containing token $x$ has target color $i$. Remember, however, that $C\_i = p(t^{-1}(i))$ and therefore that $s(C\_i) = s(p(t^{-1}(i)))$. Then by the definition of $p$ (that $t(x) = s(p(x))$), we have that $s(C\_i) = t(t^{-1}(i) = i$. Thus, for every element $x$ of $C\_i$, $s(x) = i$. Substituting this fact, we see that a sequence satisfies all the constraints if and only if for each $i$, for $x \in C\_i$, the vertex containing token $x$ has target color $s(x)$. But token $x$ has color $s(x)$, so a sequence satisfies all the constraints if and only if every token is at a vertex whose target color matches that token.

Thus we have shown that the correspondence holds: a swap corresponds to a swap, the initial situations correspond, and situations that match the "victory conditions" also correspond. Thus, since the target number of swaps $k$ is the same, the two instances are equivalent.

> **Comments:**
> **username_0**: Thanks a lot!  Your answer is correct and elegant.  
> **username_0**: I am so sorry for the wrong problem statement.  
> **username_0**: What I am looking for is that the topological order that is the most similar to the originally given sequence. The most similar means that the least number of elements is moved  

---

