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$.
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.
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, Discrete Math. Algorithms Appl. 5, No. 2, Article ID 1360003, 25 p. (2013). ZBL1294.06002.
[2] da Silva, Rodrigo Ferreira; Urrutia, Sebastián; dos Santos, Vinícius Fernandes, One-sided weak dominance drawing, Theor. Comput. Sci. 757, 36-43 (2019). ZBL1422.68186.
