# NP-hardness proof of selecting the ''fittest'' topological sequence of a DAG

Given a directed acyclic graph (DAG) with $$n$$ vertexes $$V=\{v_1, v_2,...,v_n\}$$ and a given permutation of those $$n$$ vertexes $$P=[p_1, p_2,..., p_n]$$ that $$\forall i, p_i\in V$$. Note that $$P$$ could be in any order which includes the topological order. Now we want to find the ''fittest'' topological sequence $$L=[l_1, l_2,..., l_n]$$ of the DAG that $$\forall i, l_i\in V$$.

The ''fittest'' means the difference $$D$$ between the two sequences $$P$$ and $$L$$ is minimal

$$D(P,L)=\sum_{i=1}^{n}f(p_i, l_i)$$

$$f(x,y) = \begin{cases} 0 & x = y\\ 1 & x \neq y \end{cases}$$

For example, if $$P'$$ itself is in topological order, then $$L'=P'$$ is the answer since $$D(P',L')=0$$ must be minimal.

I guess this problem is NP-hardness but couldn't prove it.

• the topological sequence of a directed acyclic graph means the result after we perform topological sorting about the directed acyclic graph. – user51340 Apr 16 at 11:31
• It would be good etiquette to accept, or at least comment on, the answer given to your related previous post here: cstheory.stackexchange.com/questions/41958/…. – Neal Young Apr 26 at 23:22
• Can you mention what (unsuccessful) attempts you've made to prove NP-hardness, or to find a poly-time algorithm? And can you give an example showing why the (presumably NP-hard) problem in your other post doesn't reduce directly to this problem? – Neal Young Apr 27 at 12:58