Consider a DAG $(V,A)$ with an initial permutation $(v_1,v_2,…,v_n)$. We want to arrange the $n$ vertices in topological order while keeping as many vertices as possible.
The problem is: Is it NP-hard to find the reordering solution with the most vertices remaining still?
Note: This came up while I was trying to update the IP tables with the minimum operations. Since IP prefixes should be placed in the order of their prefix length, some prefixes existed in IP tables should be moved around when a new prefix is going to be inserted. The operation includes writing and nullifying (note that we do not need to nullify a IP table entry before writing a new prefix into it), I want to insert a prefix with the minimum number of operations. The proposed question is actually a special case of the IP table update problem, i.e., the IP table is full after inserting the new IP prefix.
The problem has been raised in find the most similar topological ordering of a dag, but it still cannot be solved. Although one person claims to prove that it is NP-hard, but due to my limited understanding, I cannot fully understand his answer.
