7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ the topological sequence of a directed acyclic graph means the result after we perform topological sorting about the directed acyclic graph. $\endgroup$ – user51340 Apr 16 at 11:31
  • 1
    $\begingroup$ 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/…. $\endgroup$ – Neal Young Apr 26 at 23:22
  • $\begingroup$ 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? $\endgroup$ – Neal Young Apr 27 at 12:58

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.