2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – user51340 Nov 29 '18 at 15:32
  • $\begingroup$ by the way, to swap $b$ with $c$ is also an solution with one swaps $\endgroup$ – user51340 Nov 29 '18 at 15:34
  • $\begingroup$ 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 $\endgroup$ – user51340 Nov 29 '18 at 15:41
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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