Is this edge orientation optimization problem NP-hard?

Question

Is the following optimization problem NP-hard?

Problem. For a given undirected graph $G=(V,E)$, find an orientation of the edges that minimizes the objective value $\sum_\limits{v\in V} ~d_{out}(v)\times d_{in}(v)$, where $d_{out}$ (resp. $d_{in}$) is the number of out-neighbors (resp. in-neighbors).

Motivation: Assume the edge orientation does not induce any cycle of length 3, then the following algorithm lists all triangles in the input undirected graph in linear memory and in time $O(\sum_\limits{v\in V} ~d_{out}(v)\times d_{in}(v)+m+n)$ where $m$ is the number of edges and $n$ is the number of nodes.

For each node u:  
  For each out-neighbor v of node u:  
    For each out-neighbor w of node v:
      If u,w is an edge of the input undirected graph:
        output triangle u,v,w

Implementation details: the graph should be stored in a CSR-like format and, in addition, the edges of the input undirected graph should be put in a hashtable.
Finding the edge orientation that minimizes the quantity should lead to a faster algorithm. I think that the constraint "no induced cycle of length 3" is too complicated and, as a stepping stone, I've decided to formulate the above problem.
The question is related to that one where the edge orientation has to induce a DAG.

Another formulation: The problem can be written as the following Integer Quadratic Programming.

\begin{align} \text{Minimize} &\qquad \sum_{v\in V} y_v\times (d_v-y_v) &\qquad (IQP)\\ \text{s.t.} &\qquad \forall v \in V, \forall u \in N_v, x_{u,v} \in \{0,1\} \\ &\qquad \forall (u,v) \in E, x_{u,v}+x_{v,u}=1\\ &\qquad \forall v \in V, y_v=\sum_{u \in N_v} x_{u,v}\\ \end{align} with $N_v$ the set of neighbors of node $v$ in the input undirected graph and $d_v=|N_v|$.
Is (IQP) NP-hard?

Answer 1

I believe that this problem is NP-hard, here is a sketch proof (don't hesitate to ask for more details if needed).

The idea is based on a reduction from the Not-all-equal 3-SAT. For $\varphi$ a 3-SAT formula with $m$ clauses, we will build $G(\varphi)$ a graph that has minimum objective value of $2\times m$ iif $\varphi$ has a solution. Before diving into the building of $G(\varphi)$ let us show the gadgets that we will use.

Fixed node gadget: The idea here is pretty simple. To fix a node $n$ in $G(\varphi)$ we make sure that $n$ has at least $2\times m+2$ neighbors in $G(\varphi)$ by adding nodes only linked to $n$. Once a node $n$ is fixed then any orientation with objective value less or equal $2\times m$ is such that $d_{in}(n)=0$ or $d_{out}(n)=0$.

Litteral gadget: For each variable $x_i$, we will create two fixed nodes $x_i$ and $\lnot x_i$ that will be linked together with an edge. Because the two nodes are fixed and linked, in any orientation of the graph with value less than $2m$, we will have either $d_{in}(x_i)=0 \land d_{out}(\lnot x_i)=0$ or $d_{out}(x_i)=0 \land d_{in}(\lnot x_i)=0$.

Clause gadget: The idea here is slightly more intricate. For each clause $C_j = l_1 \lor l_2 \lor l_3$ we will create three nodes $C_j^1$, $C_j^2$ and $C_j^3$ which are the red nodes in the graph drawn below. In this graph the three blue nodes will correspond to the three literals $l_1$, $l_2$ and $l_3$. Since the literals will be fixed nodes, we know the orientation for the blue-red edges (i.e. the dashed edges) and we want to compute the orientation of the red-red edges (i.e. the filled edges) that minimizes the objective value.

We can easily show that either all the dashed edges are in the same direction (i.e. all blue to red or all red to blue) in which case the minimum objective value is 4 or they are in diverse directions in which case the minimum objective value is 2.

Putting everything together: If there is a solution to the not-all-equal problem we can orient the edges outward for true literals and inward for false literals and each clause triangle can be oriented in a way to have an error of $2$, therefore the overall error is $2\times m$. On the converse, if there is an orientation with error less or equal to $2\times m$ then we can retrieve a solution to the not-all-equal problem. Indeed, the fixed nodes have an in or out degree of 0 therefore we can say that literals with in degree equal to zero are true and the other are false. Since each literal is connected to its negation their value are coherent and it is a solution to the not-all-equal problem $\varphi$ because since each triangle clause has error at least 2 and the overall error is $2\times m$ it means that all triangle clauses are connected to a positive and a negative literal.