Is the following problem NP-complete?

Question

Let $G=(V,E)$ be a directed graph and let $p_{ji}$ be the minimum path weight from $j$ to $i$; Then I can obviously save the path weights in a matrix $P$ similar to an edge weight matrix;

Now the question is: Find the topological order $\pi: v_1,...,v_d$ such that the sum

$$\min\limits_{\pi \in \Pi}\sum\limits_{j,i \in V(G): \pi(j)<\pi(i)}p_{ji}$$

of all pathes is minimized; Is this problem NP-complete(or NP-hard)?

As an example for a better understanding: If the vertices are given by 1,2,3,4 and 5 and the topological order is just $\pi:1\ 2\ 3\ 4\ 5$, then the corresponding sum would be:

$$p_{12}+p_{13}+p_{14}+p_{15}+p_{23}+p_{24}+p_{25}+p_{34}+p_{35}+p_{45}$$

and for $\pi:2\ 1\ 3\ 4\ 5$ it would be

$$p_{21}+p_{23}+p_{24}+p_{25}+p_{13}+p_{14}+p_{15}+p_{34}+p_{35}+p_{45}.$$

Now I am looking for a topological order such that such a sum is minimized

Answer 1

I believe this is called the linear ordering problem, and is known to be NP-hard.

See, for example, The Linear Ordering Problem: Instances, Search Space Analysis and Algorithms