<p>I believe that this problem is NP-hard, here is a sketch proof (don't hesitate to ask for more details if needed).</p>
<p>The idea is based on a reduction from the <a href="https://en.wikipedia.org/wiki/Not-all-equal_3-satisfiability" rel="nofollow noreferrer">Not-all-equal 3-SAT</a>. For <span class="math-container">$\varphi$</span> a 3-SAT formula with <span class="math-container">$m$</span> clauses, we will build <span class="math-container">$G(\varphi)$</span> a graph that has minimum objective value of <span class="math-container">$2\times m$</span> iif <span class="math-container">$\varphi$</span> has a solution. Before diving into the  building of <span class="math-container">$G(\varphi)$</span> let us show the gadgets that we will use.</p>
<p><strong>Fixed node gadget:</strong>
The idea here is pretty simple. To fix a node <span class="math-container">$n$</span> in <span class="math-container">$G(\varphi)$</span> we make sure that <span class="math-container">$n$</span> has at least <span class="math-container">$2\times m+2$</span> neighbors in <span class="math-container">$G(\varphi)$</span> by adding nodes only linked to <span class="math-container">$n$</span>. Once a node <span class="math-container">$n$</span> is fixed then any orientation with objective value less or equal <span class="math-container">$2\times m$</span> is such that <span class="math-container">$d_{in}(n)=0$</span> or <span class="math-container">$d_{out}(n)=0$</span>.</p>
<p><strong>Litteral gadget:</strong> For each variable <span class="math-container">$x_i$</span>, we will create two fixed nodes <span class="math-container">$x_i$</span> and <span class="math-container">$\lnot x_i$</span> 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 <span class="math-container">$2m$</span>, we will have either <span class="math-container">$d_{in}(x_i)=0 \land d_{out}(\lnot x_i)=0$</span> or <span class="math-container">$d_{out}(x_i)=0 \land d_{in}(\lnot x_i)=0$</span>.</p>
<p><strong>Clause gadget:</strong> The idea here is slightly more intricate. For each clause <span class="math-container">$C_j = l_1 \lor l_2 \lor l_3$</span> we will create three nodes <span class="math-container">$C_j^1$</span>, <span class="math-container">$C_j^2$</span> and <span class="math-container">$C_j^3$</span> which are the red nodes in the graph drawn below. In this graph the three blue nodes will correspond to the three literals <span class="math-container">$l_1$</span>, <span class="math-container">$l_2$</span> and <span class="math-container">$l_3$</span>. Since the literals will be <em>fixed</em> 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.</p>
<p><a href="https://i.sstatic.net/nXWYT.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/nXWYT.png" alt="Triangle gadget" /></a></p>
<p>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.</p>
<p><strong>Putting everything together:</strong>
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 <span class="math-container">$2$</span>, therefore the overall error is <span class="math-container">$2\times m$</span>. On the converse, if there is an orientation with error less or equal to <span class="math-container">$2\times m$</span> 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 <span class="math-container">$\varphi$</span> because since each triangle clause has error at least 2 and the overall error is <span class="math-container">$2\times m$</span> it means that all triangle clauses are connected to a positive and a negative literal.</p>

CC BY-SA 4.0
2021-03-14T20:35:59.723Z
Thanks a lot! Yes, I think that your very nice proof is correct. Let me some time to make it sure. As there is no cycle in your NAE3SAT solution, I think that your proof also works if the "no induced cycle of length 3" constraint is added and for the related problem: https://cstheory.stackexchange.com/questions/38274 am I correct?
maxdan94
CC BY-SA 4.0
2021-03-14T21:42:59.080Z
I am not sure I see an ordering on the graph $G(\varphi)$ that works for your related problem… Of course in the circle of NP reduction we can find a reduction from  NAE3SAT to this related problem but it seems the page you are pointing already does that :)
For the "no induced cycle of length 3" I am not sure where you are going. There are plenty of cycles of length 3 in the graph I give and possibly some of them after orientation BUT we can transform each edge $(u,v)$ into edges $(u,w)$, $(w,z)$ and $(z,v)$ where $w$ and $z$ are fresh fixed nodes.
Louis
CC BY-SA 4.0
2021-03-14T22:01:15.930Z
After orientation, in the case it corresponds to a solution to the not-all-equal problem, there is no cycle: no cycle includes a fixed node, since $d_{in}=0$ or $d_{out}=0$; thus the only cycles can be among 3 red nodes corresponding to a clause, but the orientation with value 2 is not a cycle. Correct?
maxdan94
CC BY-SA 4.0
2021-03-15T08:26:31.920Z
Ah ok, I think you are correct. It was not clear to me that "no induced cycle of length 3" was meant for the minimal orientation.
Louis
CC BY-SA 4.0
2021-03-15T11:24:28.413Z
Ok. Well I think you solved everything...
maxdan94
CC BY-SA 4.0
2021-03-15T15:57:59.923Z
(@maxdan94 if you accept his proof it's customary to check the box to accept his answer.  That way he get's credit and stack exchange can know the question is answered.)
Neal Young
CC BY-SA 4.0
2021-03-15T16:00:47.453Z
Yes. I will do it soon. I think the proof is correct, but I have asked colleagues to double check it as I'm not comfortable with that kind of reduction.
maxdan94
CC BY-SA 4.0
2021-03-17T11:09:45.857Z
C'est bien prouvé !  Perhaps the following may help the reader a little bit: the resulting graph will have at most $3m + 2 (2m + 3) v \in O(m^2)$ nodes, where m is the number of clauses and v is the number of variables.
kerzol
CC BY-SA 4.0
2021-03-14T15:44:39.983Z
2021-03-14T15:44:39.983Z
Louis
<p>Is the following optimization problem NP-hard?</p>
<blockquote>
<p><strong>Problem.</strong> For a given undirected graph <span class="math-container">$G=(V,E)$</span>, find an orientation of the edges that minimizes the objective value <span class="math-container">$\sum_\limits{v\in V} ~d_{out}(v)\times d_{in}(v)$</span>, where <span class="math-container">$d_{out}$</span> (resp. <span class="math-container">$d_{in}$</span>) is the number of out-neighbors (resp. in-neighbors).</p>
</blockquote>
<p><strong>Motivation:</strong>
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 <span class="math-container">$O(\sum_\limits{v\in V} ~d_{out}(v)\times d_{in}(v)+m+n)$</span> where <span class="math-container">$m$</span> is the number of edges and <span class="math-container">$n$</span> is the number of nodes.</p>
<pre>
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
</pre>
<p><em>Implementation details:</em> 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.<br />
Finding the edge orientation that minimizes the quantity should lead to a faster algorithm. I think that the constraint &quot;no induced cycle of length 3&quot; is too complicated and, as a stepping stone, I've decided to formulate the above problem.<br />
The question is related to <a href="https://cstheory.stackexchange.com/questions/38274">that one</a> where the edge orientation has to induce a DAG.</p>
<p><strong>Another formulation:</strong> The problem can be written as the following Integer Quadratic Programming.</p>
<p><span class="math-container">\begin{align}
 \text{Minimize} &amp;\qquad \sum_{v\in V} y_v\times (d_v-y_v) &amp;\qquad  (IQP)\\
 \text{s.t.} &amp;\qquad \forall v \in V, \forall u \in N_v, x_{u,v}  \in \{0,1\}  \\
 &amp;\qquad \forall (u,v) \in E, x_{u,v}+x_{v,u}=1\\
 &amp;\qquad \forall v \in V, y_v=\sum_{u \in N_v} x_{u,v}\\
\end{align}</span>
with <span class="math-container">$N_v$</span> the set of neighbors of node <span class="math-container">$v$</span> in the input undirected graph and <span class="math-container">$d_v=|N_v|$</span>.<br />
Is (IQP) NP-hard?</p>

CC BY-SA 4.0
2021-03-14T22:36:14.920Z
related: https://cstheory.stackexchange.com/questions/48572/is-that-edge-orientation-optimization-problem-np-hard
Neal Young
CC BY-SA 4.0
2021-03-15T15:49:30.647Z
@NealYoung I think the (QP) relaxation does not work here as the optimization is not convex. Do you agree? No way to obtain an approximation algorithm?
maxdan94
CC BY-SA 4.0
2021-03-15T15:55:00.367Z
I agree it's not convex.  I wouldn't rule out finding an approximation algorithm by some other means.  As an aside, note that there is a zero-cost solution iff the graph is bipartite.  Maybe (for the purposes of approximation) the goal should be to minimize the current objective _plus_ m + n.  (This could be easier to approximate, and may serve as well for your purpose?)
Neal Young
<graph-theory><graph-algorithms><np-hardness><optimization><integer-programming>
Is this edge orientation optimization problem NP-hard?
maxdan94
# Is this edge orientation optimization problem NP-hard?

(Asked by: username_0 on 2021-03-12)

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?

**Tags:** graph-theory, graph-algorithms, np-hardness, optimization, integer-programming

> **Comments:**
> **username_1**: related: https://cstheory.stackexchange.com/questions/48572/is-that-edge-orientation-optimization-problem-np-hard  
> **username_0**: @NealYoung I think the (QP) relaxation does not work here as the optimization is not convex. Do you agree? No way to obtain an approximation algorithm?  
> **username_1**: I agree it's not convex.  I wouldn't rule out finding an approximation algorithm by some other means.  As an aside, note that there is a zero-cost solution iff the graph is bipartite.  Maybe (for the purposes of approximation) the goal should be to minimize the current objective _plus_ m + n.  (This could be easier to approximate, and may serve as well for your purpose?)  

---

## 1 answers

### Answer by username_2 on 2021-03-14. Score: 4 | Accepted answer

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](https://en.wikipedia.org/wiki/Not-all-equal_3-satisfiability). 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.

[![Triangle gadget](https://i.sstatic.net/nXWYT.png)](https://i.sstatic.net/nXWYT.png)

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.

> **Comments:**
> **username_0**: Thanks a lot! Yes, I think that your very nice proof is correct. Let me some time to make it sure. As there is no cycle in your NAE3SAT solution, I think that your proof also works if the "no induced cycle of length 3" constraint is added and for the related problem: https://cstheory.stackexchange.com/questions/38274 am I correct?  
> **username_2**: I am not sure I see an ordering on the graph $G(\varphi)$ that works for your related problem… Of course in the circle of NP reduction we can find a reduction from  NAE3SAT to this related problem but it seems the page you are pointing already does that :) For the "no induced cycle of length 3" I am not sure where you are going. There are plenty of cycles of length 3 in the graph I give and possibly some of them after orientation BUT we can transform each edge $(u,v)$ into edges $(u,w)$, $(w,z)$ and $(z,v)$ where $w$ and $z$ are fresh fixed nodes.  
> **username_0**: After orientation, in the case it corresponds to a solution to the not-all-equal problem, there is no cycle: no cycle includes a fixed node, since $d_{in}=0$ or $d_{out}=0$; thus the only cycles can be among 3 red nodes corresponding to a clause, but the orientation with value 2 is not a cycle. Correct?  
> **username_2**: Ah ok, I think you are correct. It was not clear to me that "no induced cycle of length 3" was meant for the minimal orientation.  
> **username_0**: Ok. Well I think you solved everything...  
> **username_1**: (@username_0 if you accept his proof it's customary to check the box to accept his answer.  That way he get's credit and stack exchange can know the question is answered.)  
> **username_0**: Yes. I will do it soon. I think the proof is correct, but I have asked colleagues to double check it as I'm not comfortable with that kind of reduction.  
> **username_3**: C'est bien prouvé !  Perhaps the following may help the reader a little bit: the resulting graph will have at most $3m + 2 (2m + 3) v \in O(m^2)$ nodes, where m is the number of clauses and v is the number of variables.  

---

