Consider your problem restricted to 3-regular graphs. Consider some ordering of the vertices. Define a split vertex to be a vertex $v$ such that both $succ(v)$ and $pred(v)$ are non-empty and define a non-split vertex to be any other vertex. Notice that in a 3-regular graph, the value of $|succ(v)| \times |pred(v)|$ is $0$ if $v$ is a non-split vertex and is $2$ otherwise.
Thus, $\sum\limits_{v\in V}|succ(v)|\times|pred(v)| = 2n_{\text{split}}$ where $n_{\text{split}}$ is the number of split vertices.
Therefore, in 3-regular graphs, solving your problem (minimizing the summation) is equivalent to choosing an ordering so as to minimize the number of split vertices.
The following theorem tells us that solving your problem in 3-regular graph $G$ is equivalent to solving Max Cut in $G$. Therefore, since Max Cut in 3-regular graphs is NP-hard, so is your problem.
Theorem If $G = (V, E)$ is a 3-regular graph with $n$ vertices then there exists an ordering of the vertices such that the number of split vertices is at most $k$ if and only if $G$ has a cut of size at least $\frac{3}{2}n - k$.
First direction
First, suppose there exists on ordering of the vertices such that the number of split vertices is at most $k$. Then we partition $V$ into two sets $A$ and $B$ as follows:
- Place all non-split vertices (under the ordering) into $A$ and $B$ by putting the vertices with 3 successors into $A$ and the vertices with 3 predecessors into $B$.
- Tentatively add all split vertices (under the ordering) into $A$.
- Repeat steps 4 and 5 until step 4 fails:
- Identify a split vertex $v$ that has more neighbors in its current set ($A$ or $B$) than in the other
- Move $v$ to the other set
The partition of $V$ into $A$ and $B$ is a cut, and each occurrence of steps 4 and 5 increases the size of that cut, so this procedure will terminate. Below we compute the size of the resulting cut.
Notice also that each split-vertex $v$ in $A$ (or $B$) has at most one neighbor in $A$ (or $B$) because otherwise this vertex would have been identified in step 4 at the final iteration of the loop. Thus, the number of edges incident on split vertices that are within $A$ or within $B$ is bounded above by the number of split vertices (which we know is at most $k$).
Next consider any edge $(u, v)$ that is not incident on a split vertex. This edge must then be between two non-split vertices. Suppose wlog that $u$ is earlier than $v$ in the ordering. Then since $u$ is a non-split vertex with a successor, it must be the case that $u$ actually has 3 successors, and similarly $v$ must have 3 predecessors. We can conclude from this that $u$ is placed in $A$ and $v$ is placed in $B$, and therefore that $(u, v)$ is not an edge within $A$ or within $B$.
Thus, we conclude that the overall number of edges within $A$ or within $B$ is at most $k$. Then the size of the cut (i.e., the number of edges not within $A$ and not within $B$) is at least $|E| - k = \frac{3}{2}n - k$.
Second direction
Now suppose there exists a cut of size at least $\frac{3}{2}n - k$. Suppose this cut partitions $V$ into sets $A$ and $B$. Then we construct an ordering of the vertices in $V$ by putting the vertices in $A$ first and the vertices in $B$ later. We claim that the number of split vertices under this ordering is at most $k$.
Consider any edge incident on a vertex in $A$. If this edge is $(u, v)$ with $u \in A$ and $v \in B$ then $v$ is a successor of $u$ since all vertices in $B$ are after all vertices in $A$. Thus, edges between $A$ and $B$ do not contribute any predecessors to any vertices in $A$. The only other possible edge incident on a vertex in $A$ is an edge within $A$. Such an edge contributes a predecessor to exactly one of its endpoints. Thus, the total over all $v \in A$ of the number of predecessors of $v$ is at most the number of edges within $A$, and so the number of vertices in $A$ with a predecessor is at most the number of edges within $A$. Since every split-vertex in $A$ is a vertex in $A$ with a predecessor, the number of split-vertices in $A$ is at most the number of edges within $A$.
Analogous logic can be used to show that the number of split-vertices in $B$ is at most the number of edges within $B$. Then the total number of split vertices under this ordering is at most the number of edges within $A$ or within $B$. Since the cut has at least $\frac{3}{2}n - k = |E| - k$ edges between $A$ and $B$, it must have at most $k$ edges within $A$ or within $B$. We conclude that the number of split vertices under the constructed ordering is at most $k$.