Skip to main content
1 of 3

find the most similar topological ordering of a dag

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$. The most similar topological order means that we use the least overwritten operations to transform $L$ to a feasible placement.