Skip to main content
Theoretical Computer Science

Return to Question

edited tags
Link
Mohammad Al-Turkistany
Mohammad Al-Turkistany
  • 21.1k
  • 5
  • 66
  • 152
Notice removed Authoritative reference needed by CommunityBot
Bounty Ended with no winning answer by CommunityBot
deleted 129 characters in body
Source Link
2016310588
2016310588
  • 33
  • 9

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.

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.

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$.

Tweeted twitter.com/StackCSTheory/status/1288398880569270273
Notice added Authoritative reference needed by 2016310588
Bounty Started worth 100 reputation by 2016310588
Source Link
2016310588
2016310588
  • 33
  • 9

find the most similar topological ordering of a dag

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.