#StackBounty: #np-hardness find the most similar topological ordering of a dag

Bounty: 100

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.

Get this bounty!!!

This site uses Akismet to reduce spam. Learn how your comment data is processed.