<p>Consider a DAG <span class="math-container">$(V,A)$</span> with an initial permutation <span class="math-container">$(v_1,v_2,…,v_n)$</span>. We want to arrange the <span class="math-container">$n$</span> vertices in topological order while keeping as many vertices as possible.</p>
<p><strong>The problem is</strong>:  Is it NP-hard to find the reordering solution with the most vertices remaining still?</p>
<p><strong>Note</strong>: 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 (<strong>note that we do not need to nullify a IP table entry before writing a new prefix into it</strong>), 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.</p>
<p>The problem has been raised in <a href="https://cstheory.stackexchange.com/questions/47286/find-the-most-similar-topological-ordering-of-a-dag">find the most similar topological ordering of a dag</a>, 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.</p>

CC BY-SA 4.0
2020-10-19T21:00:38.070Z
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.
Christian Komusiewicz
CC BY-SA 4.0
2020-10-20T01:27:47.987Z
@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.
2016310588
<np-hardness><directed-acyclic-graph><topological-sorting>
Reordering a DAG with the minimum changes
2016310588
# Reordering a DAG with the minimum changes

(Asked by: username_0 on 2020-10-17)

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](https://cstheory.stackexchange.com/questions/47286/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.

**Tags:** np-hardness, directed-acyclic-graph, topological-sorting

> **Comments:**
> **username_1**: 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.  
> **username_0**: @username_1  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.  

---

## 0 answers

