Consider a DAG $(V,A)$ with an initial permutation $(v_1,v_2,…,v_n)$. We want to arrange the $n$ vertice 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 vertice 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.

  • 2
    $\begingroup$ Wouldn't it be better to discuss the other solution instead of posting the same question twice? I will try to answer your last comment there. $\endgroup$ Oct 19 '20 at 21:00
  • $\begingroup$ @Christian Komusiewicz Thank you for your suggestion! Because I am not sure whether the answer to the original question is correct, and I contacted the respondent, because he is busy with other things. All I hope is whether anyone can understand the answer, thank you for your explanation and let my understanding goes further. By the way, can you post your comment as an answer so that you can get a reward and we can also end this question. Thanks. $\endgroup$
    – 2016310588
    Oct 20 '20 at 1:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.