#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!!!

Leave a Reply

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