<p>It is NP-hard. The reduction is from <span class="math-container">$CLIQUE$</span>, so suppose we are given an undirected graph <span class="math-container">$H$</span> on <span class="math-container">$n$</span> vertices and <span class="math-container">$m$</span> edges, with a parameter <span class="math-container">$k$</span>, and our task is to decide whether <span class="math-container">$\omega(H)\ge k$</span>. We will need some sufficiently large numbers <span class="math-container">$M\gg N \gg n$</span>, where we need about <span class="math-container">$N=n^2$</span> and <span class="math-container">$M=n^3$</span>.</p>
<p>The graph <span class="math-container">$G$</span> will have two disjoint parts. The first part will have <span class="math-container">$M+M^2$</span> vertices such that there is an arc from each of the <span class="math-container">$M$</span> vertices to each of the <span class="math-container">$M^2$</span> vertices. In the order <span class="math-container">$L$</span> the <span class="math-container">$M^2$</span> vertices will have position <span class="math-container">$M+1$</span> to <span class="math-container">$M^2+M$</span>. Since <span class="math-container">$M$</span> is huge, this implies that any optimal solution starts with the <span class="math-container">$M$</span> vertices, followed by the <span class="math-container">$M^2$</span> vertices. From the <span class="math-container">$M$</span> vertices, some can be in good position. As we can put these arbitrarily, we can easily determine this optimum; denote it by <span class="math-container">$X$</span>.</p>
<p>The second part of <span class="math-container">$G$</span> will encode <span class="math-container">$H$</span>. For every vertex of <span class="math-container">$H$</span>, <span class="math-container">$G$</span> will have <span class="math-container">$N$</span> vertices. In <span class="math-container">$L$</span> each of these will take one of the first <span class="math-container">$M$</span> positions. Because of our earlier observations, none of these can keep their original position in an optimal solution, so we should place them to make other vertices 'happy'. For every edge of <span class="math-container">$H$</span>, <span class="math-container">$G$</span> will have exactly one vertex, with <span class="math-container">$2N$</span> arcs going into it, one from each copy corresponding to one of its end-vertices. In <span class="math-container">$L$</span> each of these will have position <span class="math-container">$M^2+M+kN+1$</span> to <span class="math-container">$M^2+M+kN+m$</span>. Since after the first part of <span class="math-container">$G$</span>, we have only <span class="math-container">$kN$</span> places left before these positions, and <span class="math-container">$N\gg n$</span>, this means that at most as many of these <span class="math-container">$m$</span> vertices can be in position, as many edges can be spanned by <span class="math-container">$k$</span> vertices.</p>
<p>To summarize, we can have <span class="math-container">$M^2+X+\binom k2$</span> vertices of <span class="math-container">$G$</span> in the same position as in <span class="math-container">$L$</span> if and only if <span class="math-container">$\omega(H)\ge k$</span>.</p>
<p>ps. Notice that <span class="math-container">$G$</span> has only two levels, i.e., its longest (directed) path has length one.</p>

CC BY-SA 4.0
2020-09-02T13:51:01.980Z
I'm very sorry, due to my limited understanding, I did not fully understand your answer. For example, what does $kN$ mean, and the sentences "none of these can keep their original position in an optimal solution", and 'G will have exactly one vertex, with $2N$ arcs going into it, one from each copy corresponding to one of its end-vertices.' If you can spare your precious time to explain further, I will be very grateful to you.
2016310588
CC BY-SA 4.0
2020-10-19T21:08:31.367Z
In the description $k\cdot N$ is just a number. The $k$ comes directly from the clique instance and the $N=n^2$ where $n$ is the number of vertices in the clique instance. 'None of these can keep their original position' is true because the first $M$ positions of the solutions  must be occupied by the $M$ vertices of the "first part of the graph $G$".  These $M$ vertices are in $L$ somewhere later but in the solution they must come before their $M^2$ many outneighbors which also belong to the first part of the graph $G$.
Christian Komusiewicz
CC BY-SA 4.0
2020-07-30T10:32:52.480Z
2020-07-30T10:32:52.480Z
domotorp
<p>If I understood you question correctly, this has been studied before, or in the context of partial orders, under the name of nearest neighbor Kendall tau (NNKT) problem for a total and a partial order. Given a DAG <span class="math-container">$D$</span> you can find its transitive closure <span class="math-container">$C$</span> and define an order where <span class="math-container">$u &lt; v$</span> iff <span class="math-container">$(u,v)$</span> is an arc of <span class="math-container">$C$</span>. Similarly, a permutation can be seen as a total order.</p>
<p>Given a partial order <span class="math-container">$P$</span> and a total order <span class="math-container">$T$</span> of a given set, the objective of NNKT
is to find a linear extension of <span class="math-container">$P$</span> that has as few inversions as possible in comparison with <span class="math-container">$T$</span>. This has been shown to be NP-complete by Brandenburg et al [1]. Some related questions were considered more recently in [2]. If these are not exactly the same problem, I hope at least it shed some lite on your question.</p>
<p>[1] <em>Brandenburg, Franz J.; Gleißner, Andreas; Hofmeier, Andreas</em>, <a href="http://dx.doi.org/10.1142/S1793830913600033" rel="nofollow noreferrer"><strong>Comparing and aggregating partial orders with Kendall tau distances</strong></a>, Discrete Math. Algorithms Appl. 5, No. 2, Article ID 1360003, 25 p. (2013). <a href="https://zbmath.org/?q=an:1294.06002" rel="nofollow noreferrer">ZBL1294.06002</a>.</p>
<p>[2] <em>da Silva, Rodrigo Ferreira; Urrutia, Sebastián; dos Santos, Vinícius Fernandes</em>, <a href="http://dx.doi.org/10.1016/j.tcs.2018.07.012" rel="nofollow noreferrer"><strong>One-sided weak dominance drawing</strong></a>, Theor. Comput. Sci. 757, 36-43 (2019). <a href="https://zbmath.org/?q=an:1422.68186" rel="nofollow noreferrer">ZBL1422.68186</a>.</p>

CC BY-SA 4.0
2020-08-06T19:47:07.907Z
But the OP asks, given a partial order P and a total order T, for a total order T' that is a linear extension of P and minimizes the number of vertices v such that v's rank in T' differs from its rank in T.  In general, this is not the same as minimizing the number of inversions of T w.r.t. T' (the problem you give references for).
Neal Young
CC BY-SA 4.0
2020-08-13T01:26:10.790Z
Thank you for your guidance. I have studied the articles you listed, but found that the problem is different from mine. Nevertheless, your answer did give me some ideas, thank you very much.
2016310588
CC BY-SA 4.0
2020-08-01T22:11:52.433Z
2020-08-01T22:11:52.433Z
Vinicius dos Santos
<p>Given a permutation <span class="math-container">$L$</span> of the <span class="math-container">$n$</span> vertices of the directed acyclic graph <span class="math-container">$G=(V,E)$</span>.</p>
<p>Question: is it NP-hard to find the topological order of the <span class="math-container">$G$</span> that is the most similar to the given permutation <span class="math-container">$L$</span>?</p>
<p>(The most similar is that the least number of elements' positions are changed.)</p>
<p>Note: the topological order means the <span class="math-container">$n$</span> elements should be placed according to the constraints in <span class="math-container">$G$</span>.</p>

CC BY-SA 4.0
2020-07-27T14:01:14.260Z
Here are two other posts about NP-hard problems that ask for a topological ordering of a DAG that is optimal by some measure: https://cstheory.stackexchange.com/questions/31975/lexicographically-minimal-topological-sort-of-a-labeled-dag/31993#31993, https://cstheory.stackexchange.com/questions/36230/ordering-of-a-dag-minimizing-some-definition-of-cost.  Maybe these will give some ideas for coming up with an NP-hardness proof.
Neal Young
CC BY-SA 4.0
2020-07-28T01:12:48.247Z
Thanks a lot for your help ! I will study these two issues carefully to see if there is a connection.
2016310588
CC BY-SA 4.0
2020-07-29T13:10:35.393Z
I'm not entirely sure which metric you're using for "most similar". When evaluating a potential ordering $O$, do you (a) try to minimize the number of positions where $O$ is different from $L$, (b) try to minimize the number of swaps needed to get from $O$ to $L$, or (c) something else? Different parts of your question point to either (a) or (b), but they are different metrics, so the answer can depend on which you meant.
Mikhail Rudoy
CC BY-SA 4.0
2020-07-29T15:34:07.217Z
@Mikhail Rudoy thanks for your attention! I am sorry for the ambiguity. (a) is the exact metric.
2016310588
CC BY-SA 4.0
2020-07-29T16:11:07.870Z
So just to make sure I have the idea right, here's the problem I think you are asking about: you are given a DAG with $n$ vertices labeled $1$ through $n$; the goal is to rearrange the labels such that under the new labeling scheme, the order implied by the new labels is a topological sort of the DAG and such that the number of vertices keeping their original labels is maximized. Is that right? Thanks!
Mikhail Rudoy
CC BY-SA 4.0
2020-07-30T01:17:19.010Z
@MikhailRudoy Yes, your understanding is correct.
2016310588
CC BY-SA 4.0
2020-07-30T01:37:40.637Z
@MikhailRudoy By the way, our purpose is not to find the least number of label exchanges (or, swaps) but to find the least number of vertices whose label has been changed.
2016310588
CC BY-SA 4.0
2021-08-16T21:55:44.683Z
What is the motivation for your question?
Mohammad Al-Turkistany
CC BY-SA 4.0
2021-08-17T02:52:53.203Z
@Mohammad Al-Turkistany   ``TCAM'', the hardware for rule table lookup, requires rules to be placed in their topological order. When we want to insert a new rule $r$ to the TCAM, some rule has to be relocated. Since the TCAM only provides two types of equal-cost operations: write and nullify, we want to calculate the minimum number of TCAM operations to insert the new rule $r_u$.
2016310588
CC BY-SA 4.0
2021-08-17T03:11:20.970Z
@MohammadAl-Turkistany  the proposed question is actually a special case of the original problem. suppose there is only one empty TCAM entry at the bottom of TCAM, i.e., after the insertion of $r_u$, TCAM is completely occupied.
We might as well put $r_u$ into the only empty TCAM entry and the corresponding TCAM layout is $L$.
Since such rule placement may violate the topological order, we need to relocate some rules.
In this case, it easy to see that , the rule (including $r_u$) topological order which is the most similar to $L$ corresponds to the minimum TCAM operations.
2016310588
<np-hardness><directed-acyclic-graph><partial-order><topological-sorting>
find the most similar topological ordering of a dag
2016310588
# find the most similar topological ordering of a dag

(Asked by: username_0 on 2020-07-27)

Given a permutation $L$ of the $n$ vertices of the directed acyclic graph $G=(V,E)$.

Question: is it NP-hard to find the topological order of the $G$ that is the most similar to the given permutation $L$?

(The most similar is that the least number of elements' positions are changed.)

Note: the topological order means the $n$ elements should be placed according to the constraints in $G$.

**Tags:** np-hardness, directed-acyclic-graph, partial-order, topological-sorting

> **Comments:**
> **username_1**: Here are two other posts about NP-hard problems that ask for a topological ordering of a DAG that is optimal by some measure: https://cstheory.stackexchange.com/questions/31975/lexicographically-minimal-topological-sort-of-a-labeled-dag/31993#31993, https://cstheory.stackexchange.com/questions/36230/ordering-of-a-dag-minimizing-some-definition-of-cost.  Maybe these will give some ideas for coming up with an NP-hardness proof.  
> **username_0**: Thanks a lot for your help ! I will study these two issues carefully to see if there is a connection.  
> **username_2**: I'm not entirely sure which metric you're using for "most similar". When evaluating a potential ordering $O$, do you (a) try to minimize the number of positions where $O$ is different from $L$, (b) try to minimize the number of swaps needed to get from $O$ to $L$, or (c) something else? Different parts of your question point to either (a) or (b), but they are different metrics, so the answer can depend on which you meant.  
> **username_0**: @username_2 thanks for your attention! I am sorry for the ambiguity. (a) is the exact metric.  
> **username_2**: So just to make sure I have the idea right, here's the problem I think you are asking about: you are given a DAG with $n$ vertices labeled $1$ through $n$; the goal is to rearrange the labels such that under the new labeling scheme, the order implied by the new labels is a topological sort of the DAG and such that the number of vertices keeping their original labels is maximized. Is that right? Thanks!  
> **username_0**: @MikhailRudoy Yes, your understanding is correct.  
> **username_0**: @MikhailRudoy By the way, our purpose is not to find the least number of label exchanges (or, swaps) but to find the least number of vertices whose label has been changed.  
> **username_3**: What is the motivation for your question?  
> **username_0**: @username_3   ``TCAM'', the hardware for rule table lookup, requires rules to be placed in their topological order. When we want to insert a new rule $r$ to the TCAM, some rule has to be relocated. Since the TCAM only provides two types of equal-cost operations: write and nullify, we want to calculate the minimum number of TCAM operations to insert the new rule $r_u$.  
> **username_0**: @MohammadAl-Turkistany  the proposed question is actually a special case of the original problem. suppose there is only one empty TCAM entry at the bottom of TCAM, i.e., after the insertion of $r_u$, TCAM is completely occupied. We might as well put $r_u$ into the only empty TCAM entry and the corresponding TCAM layout is $L$. Since such rule placement may violate the topological order, we need to relocate some rules. In this case, it easy to see that , the rule (including $r_u$) topological order which is the most similar to $L$ corresponds to the minimum TCAM operations.  

---

## 2 answers

### Answer by username_4 on 2020-07-30. Score: 2 | Accepted answer

It is NP-hard. The reduction is from $CLIQUE$, so suppose we are given an undirected graph $H$ on $n$ vertices and $m$ edges, with a parameter $k$, and our task is to decide whether $\omega(H)\ge k$. We will need some sufficiently large numbers $M\gg N \gg n$, where we need about $N=n^2$ and $M=n^3$.

The graph $G$ will have two disjoint parts. The first part will have $M+M^2$ vertices such that there is an arc from each of the $M$ vertices to each of the $M^2$ vertices. In the order $L$ the $M^2$ vertices will have position $M+1$ to $M^2+M$. Since $M$ is huge, this implies that any optimal solution starts with the $M$ vertices, followed by the $M^2$ vertices. From the $M$ vertices, some can be in good position. As we can put these arbitrarily, we can easily determine this optimum; denote it by $X$.

The second part of $G$ will encode $H$. For every vertex of $H$, $G$ will have $N$ vertices. In $L$ each of these will take one of the first $M$ positions. Because of our earlier observations, none of these can keep their original position in an optimal solution, so we should place them to make other vertices 'happy'. For every edge of $H$, $G$ will have exactly one vertex, with $2N$ arcs going into it, one from each copy corresponding to one of its end-vertices. In $L$ each of these will have position $M^2+M+kN+1$ to $M^2+M+kN+m$. Since after the first part of $G$, we have only $kN$ places left before these positions, and $N\gg n$, this means that at most as many of these $m$ vertices can be in position, as many edges can be spanned by $k$ vertices.

To summarize, we can have $M^2+X+\binom k2$ vertices of $G$ in the same position as in $L$ if and only if $\omega(H)\ge k$.

ps. Notice that $G$ has only two levels, i.e., its longest (directed) path has length one.

> **Comments:**
> **username_0**: I'm very sorry, due to my limited understanding, I did not fully understand your answer. For example, what does $kN$ mean, and the sentences "none of these can keep their original position in an optimal solution", and 'G will have exactly one vertex, with $2N$ arcs going into it, one from each copy corresponding to one of its end-vertices.' If you can spare your precious time to explain further, I will be very grateful to you.  
> **username_5**: In the description $k\cdot N$ is just a number. The $k$ comes directly from the clique instance and the $N=n^2$ where $n$ is the number of vertices in the clique instance. 'None of these can keep their original position' is true because the first $M$ positions of the solutions  must be occupied by the $M$ vertices of the "first part of the graph $G$".  These $M$ vertices are in $L$ somewhere later but in the solution they must come before their $M^2$ many outneighbors which also belong to the first part of the graph $G$.  

---

### Answer by username_6 on 2020-08-01. Score: 0

If I understood you question correctly, this has been studied before, or in the context of partial orders, under the name of nearest neighbor Kendall tau (NNKT) problem for a total and a partial order. Given a DAG $D$ you can find its transitive closure $C$ and define an order where $u < v$ iff $(u,v)$ is an arc of $C$. Similarly, a permutation can be seen as a total order.

Given a partial order $P$ and a total order $T$ of a given set, the objective of NNKT
is to find a linear extension of $P$ that has as few inversions as possible in comparison with $T$. This has been shown to be NP-complete by Brandenburg et al [1]. Some related questions were considered more recently in [2]. If these are not exactly the same problem, I hope at least it shed some lite on your question.

[1] *Brandenburg, Franz J.; Gleißner, Andreas; Hofmeier, Andreas*, [**Comparing and aggregating partial orders with Kendall tau distances**](http://dx.doi.org/10.1142/S1793830913600033), Discrete Math. Algorithms Appl. 5, No. 2, Article ID 1360003, 25 p. (2013). [ZBL1294.06002](https://zbmath.org/?q=an:1294.06002).

[2] *da Silva, Rodrigo Ferreira; Urrutia, Sebastián; dos Santos, Vinícius Fernandes*, [**One-sided weak dominance drawing**](http://dx.doi.org/10.1016/j.tcs.2018.07.012), Theor. Comput. Sci. 757, 36-43 (2019). [ZBL1422.68186](https://zbmath.org/?q=an:1422.68186).

> **Comments:**
> **username_1**: But the OP asks, given a partial order P and a total order T, for a total order T' that is a linear extension of P and minimizes the number of vertices v such that v's rank in T' differs from its rank in T.  In general, this is not the same as minimizing the number of inversions of T w.r.t. T' (the problem you give references for).  
> **username_0**: Thank you for your guidance. I have studied the articles you listed, but found that the problem is different from mine. Nevertheless, your answer did give me some ideas, thank you very much.  

---

