<h3>Summary</h3>
<ol>
<li><p>OP's problem has a polynomial-time algorithm via reduction to min-cost bipartite matching. (Lemma 1, below.)</p>
</li>
<li><p>Alternatively, one can strengthen OP's relaxation QP directly, by modeling the cost more carefully, to make QP it into a linear program (LP) with no integrality gap, so that any basic feasible solution to the LP gives an optimal solution to the original program (IQP).  (Lemma 2, below.)</p>
</li>
<li><p>An approximate solution to IQP can be obtained by randomized rounding: the natural randomized-rounding scheme gives a 2-approximation, and a <span class="math-container">$(1+1/\overline d)$</span>-approximation in graphs with average degree <span class="math-container">$\overline d$</span>. (Note that any connected graph has average degree at least <span class="math-container">$2-2/|V|$</span>.)  (Lemmas 4 and 5, below.)</p>
</li>
</ol>
<hr />
<h3>1. Reduction to min-cost matching</h3>
<p><strong>Lemma 1.</strong> <em>The problem in the post has a polynomial-time algorithm via reduction to  min-cost bipartite matching.</em></p>
<p><em>Proof of Lemma 1.</em> Given an instance <span class="math-container">$G=(V,E)$</span> of the problem in the post, the reduction constructs an edge-weighted bipartite graph <span class="math-container">$G'=(U, W, E')$</span> as follows.</p>
<ol>
<li><p>For each edge <span class="math-container">$e\in E$</span>, add a vertex <span class="math-container">$\alpha_{e}$</span> to <span class="math-container">$U$</span>.</p>
</li>
<li><p>For each vertex <span class="math-container">$v\in V$</span>, add <span class="math-container">$d_G(v)$</span> vertices <span class="math-container">$\beta^v_1, \beta^v_2, \ldots, \beta^v_{d_v}$</span> to <span class="math-container">$W$</span>, where <span class="math-container">$d_G(v)$</span> is the degree of <span class="math-container">$v$</span>.</p>
</li>
<li><p>For each edge <span class="math-container">$e\in E$</span> and vertex <span class="math-container">$v\in e$</span>, add edges <span class="math-container">$(\alpha_e, \beta^v_i)$</span> for <span class="math-container">$i\in[d_G(v)]$</span> to <span class="math-container">$E'$</span>.  Give each edge <span class="math-container">$(\alpha_e, \beta^v_i)$</span> cost <span class="math-container">$i^2-(i-1)^2$</span>.</p>
</li>
</ol>
<p>The problem is then to find a minimum-cost maximum matching <span class="math-container">$M$</span> in <span class="math-container">$G'$</span>, that is, a matching of minimum cost among those having exactly one edge incident to each vertex <span class="math-container">$\alpha_e\in U$</span>.  This problem can be solved in polynomial time by standard algorithms for min-cost matching, or by reduction to min-cost flow.  Clearly the reduction can be implemented in polynomial time.</p>
<p>To see that the reduction is correct, note that, given any orientation of the edges of <span class="math-container">$G$</span>, there is a corresponding matching <span class="math-container">$M$</span>: for each edge <span class="math-container">$e\in E$</span>, match the vertex <span class="math-container">$\alpha_e$</span> to the vertex <span class="math-container">$\beta^v_i$</span>, where <span class="math-container">$v\in e$</span> is the vertex that the oriented <span class="math-container">$e$</span> leaves, and <span class="math-container">$\beta^v_i$</span> is chosen greedily to be the first not-already-matched vertex in <span class="math-container">$\beta^v_1, \beta^v_2, \ldots, \beta^v_{d_G(v)}$</span>.  Then <span class="math-container">$d_{\text{out}}(v)$</span> of these vertices are matched, at total cost <span class="math-container">$\sum_{i=1}^{d_{\text{out}}(v)} i^2 - (i-1)^2$</span>, which (as the sum telescopes) equals <span class="math-container">$d_{\text{out}}(v)^2$</span>, so the total cost of the matching <span class="math-container">$M$</span> in <span class="math-container">$G'$</span> equals <span class="math-container">$\sum_{v\in V} d_{\text{out}}(v)^2$</span>, as desired.</p>
<p>Conversely, let <span class="math-container">$M$</span> be any matching in <span class="math-container">$G'$</span> among those with an edge incident to each vertex <span class="math-container">$\alpha_e\in U$</span>.  Construct a corresponding orientation of <span class="math-container">$E$</span> as follows.  For each edge <span class="math-container">$e\in E$</span>, let <span class="math-container">$\beta^v_i$</span> be the vertex that <span class="math-container">$\alpha_e$</span> is matched to (so <span class="math-container">$v\in e$</span>).  Then orient <span class="math-container">$e$</span> out of <span class="math-container">$v$</span>.  The cost of <span class="math-container">$M$</span> is then at least <span class="math-container">$\sum_{v\in V} d_{\text{out}}(v)^2$</span>, because in <span class="math-container">$M$</span> for each <span class="math-container">$v\in V$</span> there are <span class="math-container">$d_{\text{out}}(v)$</span> edges matched to vertices in <span class="math-container">$\{\beta^v_i : i\in d_G(v)\}$</span>, so (by the convexity of the function <span class="math-container">$i\mapsto i^2$</span>) the cost of these edges in <span class="math-container">$M$</span> is at least <span class="math-container">$d_{\text{out}}(v)^2$</span>.  So the cost <span class="math-container">$\sum_{v\in V} d_{\text{out}}(v)^2$</span> of the orientation is at most the cost of <span class="math-container">$M$</span>, as desired.</p>
<p>It follows that, given a minimum-cost matching in <span class="math-container">$G'$</span>, the corresponding orientation in <span class="math-container">$G$</span> minimizes <span class="math-container">$\sum_{v\in V} d_{\text{out}}(v)^2$</span>, as desired. <span class="math-container">$~~~\Box$</span></p>
<hr />
<h3>2. Adjusting the quadratic program yields an LP with no integrality gap</h3>
<p>Following the idea underlying Lemma 1, consider modifying OP's quadratic program by replacing the quadratic objective <span class="math-container">$\sum_{u\in V} y_u^2$</span> by <span class="math-container">$\sum_{u\in V} f(y_u)$</span>, where <span class="math-container">$f(z)$</span> is the piecewise-linear function with integer breakpoints such that <span class="math-container">$f(z) = z^2$</span> for integer <span class="math-container">$z$</span>.  (Note that <span class="math-container">$z^2 &lt; f(z)$</span> for non-integer <span class="math-container">$z$</span>, yet <span class="math-container">$f$</span> is still convex, so this strengthens the relaxation.)</p>
<p>This modified program can in fact be formulated as a linear program by introducing additional non-negative variables <span class="math-container">$\{\Delta^u_i : u\in V, i\in [d_G(u)]\}$</span> to model the cost, as follows:</p>
<p><span class="math-container">$$
\begin{align}
\text{minimize} &amp; \sum_{u\in V} \sum_{i=1}^{d_G(u)} (i^2-(i-1)^2)\Delta^u_i \\
(\forall u\in V) &amp; \sum_{i=1}^{d_G(u)} \Delta^u_i \ge y_u\\
&amp; \vdots~~~~~(\text{the rest is the same as OP's program QP})
\end{align}
$$</span></p>
<p><strong>Lemma 2.</strong> <em>The optimal basic feasible solutions to the above LP are 0/1 solutions.</em></p>
<p><em>Proof idea.</em> One can show that the LP equivalent to the (standard relaxation of) the matching problem in Lemma 1, in that the solutions of the two programs correspond by a correspondence that preserves cost, integrality, and the property of being a basic feasible solution.  <span class="math-container">$~~~\Box$</span></p>
<hr />
<h3>3. Approximation ratio for randomized rounding of QP (Lemmas 3-5)</h3>
<p>Here's the rounding scheme. Given a fractional solution <span class="math-container">$x$</span> for QP, define 0/1 solution <span class="math-container">$x'$</span> as follows: for each edge <span class="math-container">$(u,w)$</span> independently: take <span class="math-container">$x'_{uw} = 1$</span> and <span class="math-container">$x'_{wu}=0$</span> with probability <span class="math-container">$x_{uw}$</span>; otherwise take <span class="math-container">$x'_{uw} = 0$</span> and <span class="math-container">$x'_{wu} = 1$</span>.</p>
<p>Let <span class="math-container">$f(x)$</span> be the objective function of QP.</p>
<p><strong>Lemma 3.</strong> <em>For any feasible <span class="math-container">$x$</span>,</em>
<span class="math-container">$$E[f(x')] = f(x) + 2\sum_{(u,w)\in E} x_{uw}x_{wu} \le f(x) + |E|/2.$$</span></p>
<p><em>Proof.</em> This is a standard calculation.  Note that
<span class="math-container">$$f(x) = \sum_{u\in V} \Big(
\sum_{w\in N(u)} x^2_{uw} + 2\sum_{w'\in N(u), w'\ne w} x_{uw}x_{uw'}\Big)$$</span>
and by linearity of expectation, the independence of <span class="math-container">$x'_{uw}$</span> and <span class="math-container">$x'_{uw'}$</span>, and <span class="math-container">$E[x'^2_{uw}] = x_{uw}$</span>,
<span class="math-container">$$E[f(x')] = \sum_{u\in V} \Big(
\sum_{w\in N(u)} x_{uw} + 2\sum_{w'\in N(u), w'\ne w} x_{uw}x_{uw'}\Big).$$</span>
Using this and <span class="math-container">$x_{uw} = 1 - x_{wu}$</span>,
<span class="math-container">$$
E[f(x')] - f(x) 
= \sum_{(u,w)\in E} x_{uw} - x^2_{uw} + x_{wu} - x^2_{wu}
= 2\sum_{(u,w)\in E} x_{uw} x_{wu}.$$</span></p>
<p><strong>Lemma 4.</strong> <em>For any feasible <span class="math-container">$x$</span>, <span class="math-container">$E[f(x')] \le 2 f(x)$</span>. That is, the rounding scheme gives a 2-approximation.</em></p>
<p><em>Proof.</em>
By inspection of the expansion of <span class="math-container">$f(x)$</span> in the proof of Lemma 3,
<span class="math-container">$$f(x) \ge \sum_{(u,w)\in E} x^2_{uw} + x^2_{wu}.$$</span>
Applying <span class="math-container">$p^2 + (1-p)^2 \ge 2p(1-p)$</span> for <span class="math-container">$p\in[0,1]$</span> (with <span class="math-container">$p=x_{uw}$</span>)
to each term gives
<span class="math-container">$$f(x) \ge 2\sum_{(u,w)\in E} x_{uw}x_{wu}.$$</span>
This and Lemma 3 imply <span class="math-container">$E[f(x')] \le f(x) + f(x) = 2 f(x)$</span>. <span class="math-container">$~~~\Box$</span></p>
<p>The bound is tight in that for any graph with maximum degree 1,
the fractional solution <span class="math-container">$x_{uw} = x_{wu} = 1/2$</span> obtains value <span class="math-container">$|E|/2$</span>,
but any integer solution has value <span class="math-container">$|E|$</span>.
(Also note that <span class="math-container">$|E|$</span> is a lower bound on OPT,
using <span class="math-container">$\sum_{u\in V} d^2_{out}(v) \ge \sum_{u\in V} d_{out}(v) = |E|$</span>.)</p>
<p><strong>Lemma 5.</strong> <em>In any graph with average degree <span class="math-container">$\overline d = 2|E|/|V|$</span>, the rounding scheme gives at least a <span class="math-container">$(1+1/\overline d)$</span>-approximation.</em></p>
<p><em>Proof.</em>  Fix an optimal solution. Let <span class="math-container">$d'_v$</span> denote the out-degree of vertex <span class="math-container">$v$</span> in the optimal solution,
so <span class="math-container">$d'$</span> is a vector in <span class="math-container">$\mathbb R_+^{|V|}$</span>.
Let <span class="math-container">$\mathbf 1$</span> denote the all-ones vector in <span class="math-container">$\mathbb R^{|V|}$</span>.
By <a href="https://en.wikipedia.org/wiki/Cauchy%E2%80%93Schwarz_inequality" rel="nofollow noreferrer">Cauchy-Schwarz</a>,
<span class="math-container">$$\text{OPT} = d' \cdot d' 
\ge (d' \cdot \mathbf 1)^2/(\mathbf 1\cdot \mathbf 1) 
= \textstyle \big(\sum_v d'_v\big)^2/|V| 
= |E|^2/|V| = |E|\overline d/2.$$</span>
By this and Lemma 1
<span class="math-container">$$E[f(x')] \le f(x) + |E|/2 \le f(x) + \text{OPT} / \overline d \le \text{OPT}(1+1/\overline d).$$</span>
<span class="math-container">$~~~\Box$</span></p>

CC BY-SA 4.0
2021-03-14T23:01:53.860Z
Thanks a lot. Wonderful! I think $E[x'^2_{uw} = x_{uw}]$ should be  $E[x'^2_{uw}] = x_{uw}$. I do not understand why OPT is at least $|E|^2/|V|$.
maxdan94
CC BY-SA 4.0
2021-03-15T02:30:13.043Z
Good catch.  I edited the post to explain.
Neal Young
CC BY-SA 4.0
2021-03-14T22:02:41.003Z
2022-12-05T14:49:10.300Z
2022-12-05T14:49:10.300Z
Neal Young
<p><strong>Definition:</strong> Given an undirected graph <span class="math-container">$G$</span> and an edge orientation <span class="math-container">$\vec{G}$</span>, an unstable path is a directed path that goes from a node <span class="math-container">$s$</span> to a node <span class="math-container">$t$</span>, such that the out-degree of node <span class="math-container">$s$</span> is strictly larger than the out-degree of node <span class="math-container">$t$</span> plus one. We observe that flipping the orientation of all edges along that path decreases the cost.</p>
<p><strong>Unstable path algorithm:</strong> Start from an arbitrary edge orientation and as long as an unstable path exists flip the direction of all edges along that path.</p>
<p><strong>Theorem:</strong> The unstable path algorithm is optimal and can be implemented to run in polynomial time.</p>
<p><strong>Proof:</strong> If an unstable path exits, it can be found by running at most <span class="math-container">$n=|V|$</span> BFS and since flipping an unstable path decreases the cost, which is an integer bounded by <span class="math-container">$n^3$</span>, the algorithm can be implemented in <span class="math-container">$O(n^6)$</span> time.</p>
<p>Clearly, there is no unstable path in an optimal orientation as flipping an unstable path decreases the cost. We thus only need to prove that if an orientation is stable (i.e. does not have an unstable path), then the orientation is optimal. We prove that any stable orientation has the same cost, which is thus optimal as an optimal orientation is stable.</p>
<p>Let <span class="math-container">$\vec{G_1}$</span> and <span class="math-container">$\vec{G_2}$</span> be two stable orientations of the same undirected graph <span class="math-container">$G$</span>. We prove that the out-degree distribution of <span class="math-container">$\vec{G_1}$</span> and <span class="math-container">$\vec{G_2}$</span> are the same and thus they have the same cost.</p>
<p>We first define the notion of a <span class="math-container">$k$</span>-level for an orientation <span class="math-container">$\vec{G}$</span>. The <span class="math-container">$k$</span>-level of <span class="math-container">$\vec{G}$</span> is the set of all nodes reachable (taking into account orientation) from a node with out-degree <span class="math-container">$k$</span> or more (in particular, it contains all nodes with out-degree <span class="math-container">$k$</span>). In a stable graph, the <span class="math-container">$k$</span>-level can only have nodes of out-degree <span class="math-container">$k-1$</span> or higher as each node in a <span class="math-container">$k$</span>-level is reachable from some node with out-degree <span class="math-container">$k$</span> and there is no unstable path.</p>
<p>Now, let us prove that, for all <span class="math-container">$k$</span>'s, the <span class="math-container">$k$</span>-levels of <span class="math-container">$\vec{G_1}$</span> and <span class="math-container">$\vec{G_2}$</span> are equal. We prove that the <span class="math-container">$k$</span>-level of <span class="math-container">$\vec{G_1}$</span> is included in the one of <span class="math-container">$\vec{G_2}$</span>  and thus, by symmetry, they are equal. For a given <span class="math-container">$k$</span>, let C be the set of nodes in the <span class="math-container">$k$</span>-level of <span class="math-container">$\vec{G_1}$</span> and in the <span class="math-container">$k$</span>-level of <span class="math-container">$\vec{G_2}$</span> and let <span class="math-container">$T$</span> be the set of nodes in the <span class="math-container">$k$</span>-level of <span class="math-container">$\vec{G_1}$</span> but not  in the <span class="math-container">$k$</span>-level of <span class="math-container">$\vec{G_2}$</span>.  In <span class="math-container">$\vec{G_2}$</span>, there cannot be any edge from <span class="math-container">$C$</span> to <span class="math-container">$T$</span> as <span class="math-container">$T$</span> is not in the <span class="math-container">$k$</span>-level of  <span class="math-container">$\vec{G_2}$</span>. In <span class="math-container">$\vec{G_1}$</span>, any edge with source in <span class="math-container">$T$</span> has target in <span class="math-container">$C$</span> or <span class="math-container">$T$</span>, these edges are also in <span class="math-container">$\vec{G_2}$</span> some of them with source and target in <span class="math-container">$T$</span> can be reversed. If <span class="math-container">$T$</span> is not empty, then we have at least one edge in <span class="math-container">$\vec{G_1}$</span> from <span class="math-container">$C$</span> to <span class="math-container">$T$</span> (and this edge is from <span class="math-container">$T$</span> to <span class="math-container">$C$</span> in <span class="math-container">$\vec{G_2}$</span>) or at least one node in <span class="math-container">$T$</span> with out-degree <span class="math-container">$k$</span>, therefore the total number of edges starting in <span class="math-container">$T$</span> in <span class="math-container">$\vec{G_2}$</span> is at least <span class="math-container">$|T|\times (k-1) + 1$</span> which means that at least one node in <span class="math-container">$T$</span> has out-degree <span class="math-container">$k$</span> which is impossible and thus <span class="math-container">$T$</span> is empty and the <span class="math-container">$k$</span>-levels of <span class="math-container">$\vec{G_1}$</span> and <span class="math-container">$\vec{G_2}$</span> are equal.</p>
<p>We define a <span class="math-container">$k$</span>-level node as a node in the <span class="math-container">$k$</span>-level, but not in the <span class="math-container">$(k+1)$</span>-level. An edge can only go from a <span class="math-container">$k$</span>-level node to a <span class="math-container">$k'$</span>-level node with <span class="math-container">$k'\geq k$</span>, therefore since the <span class="math-container">$k$</span>-levels are the same in <span class="math-container">$\vec{G_1}$</span> and <span class="math-container">$\vec{G_2}$</span>, the number of edges starting from a <span class="math-container">$k$</span>-level node is the same in <span class="math-container">$\vec{G_1}$</span> and <span class="math-container">$\vec{G_2}$</span> and since each <span class="math-container">$k$</span>-level node has out-degree <span class="math-container">$k$</span> or <span class="math-container">$k-1$</span>, the number of nodes with out-degree <span class="math-container">$k$</span> (resp. <span class="math-container">$k-1$</span>) among the <span class="math-container">$k$</span>-level nodes is the same in <span class="math-container">$\vec{G_1}$</span> and <span class="math-container">$\vec{G_2}$</span>. We conclude that, as the <span class="math-container">$k$</span>-level nodes are the same, the degree distribution of <span class="math-container">$\vec{G_1}$</span> and <span class="math-container">$\vec{G_2}$</span> are the same and they have the same cost.</p>

CC BY-SA 4.0
2021-03-17T14:42:43.263Z
Wow!! Yes, I think your polynomial time algorithm is correct. Let me some time to make it sure. I think the proof can be made shorter and clearer.
maxdan94
CC BY-SA 4.0
2021-03-17T14:43:03.857Z
The idea of unstable path is very nice, it makes me think of the [Ford-Fulkerson algorithm](https://en.wikipedia.org/wiki/Ford%E2%80%93Fulkerson_algorithm) for maxflow-mincut. Is there a link between the two problems?
maxdan94
CC BY-SA 4.0
2021-03-17T14:44:05.350Z
I think this defines a new graph decomposition similar to [the k-core decomposition](https://en.wikipedia.org/wiki/Degeneracy_(graph_theory)) and [the density-friendly decomposition](https://papers-gamma.link/paper/7). I believe the decomposition is interesting by itself.
maxdan94
CC BY-SA 4.0
2021-03-17T16:44:01.277Z
I also had in mind the Ford-Fulkerson but I haven't found the link between the two... 

For the $k$-core decomposition I have heard about it in my life but I am not very familiar with the concept or its application but it does seem very related!
Louis
CC BY-SA 4.0
2021-03-18T14:20:54.957Z
I don't understand the sentence "The k-level of G is the smallest S that contains all nodes with an out degree greater than k plus all the nodes pointed by a node in S.": is it a recursive definition in that a node of out-degree k can point another node that can point to another node? Have you tried a reductio ad absurdum: "Assume the graph is stable and not optimal"?
maxdan94
CC BY-SA 4.0
2021-03-18T17:21:22.107Z
When you say "a path", it is a path in the directed graph, taking into account edge orientation (i.e. you cannot have an edge in the other direction along the path)?
maxdan94
CC BY-SA 4.0
2021-03-19T11:09:42.367Z
The levels are indeed defined recursively. I have modified the definition to "a $k$-level contains all the nodes reachable (following orientation) from a node of degree higher or equal to $k$". When I say a path, I do take into account the orientation.
Louis
CC BY-SA 4.0
2021-03-19T11:16:15.247Z
I lookedat the correlation between $k$-core and $k$-levels, we can probably get a bound on the $k$-coreness of a $k$-level node and vice-versa but we cannot deduce exactly the $k$-coreness of a node from its $k$-levelness and vice-versa. 

Indeed:  in a $3$-clique, all nodes are $2$-core and are $1$-level;
 with a $4$-clique plus a node $n$ with two edges towards nodes of the $4$-clique then $n$ is $2$-core but $n$ is $2$-level; if we have a $2$-cliques, the nodes are $1$-level ans $1$-core.
Overall a node can be 1-level and 1 or 2-core and 2-core but 1 or 2-level.
Louis
CC BY-SA 4.0
2022-12-04T00:23:20.520Z
@Louis, I accidentally down-voted your answer and the web site would not let me correct that until the post was edited. So I edited the post (making no actual change) just so I could change the down vote to an up vote. Please feel free to roll back the edit! Sorry about that. Also, note that I edited a new answer into my answer, describing a reduction to min-cost flow.
Neal Young
CC BY-SA 4.0
2021-03-17T11:51:31.037Z
2022-12-03T00:16:31.207Z
2022-12-03T00:16:31.207Z
Louis
<p>Note that the <a href="https://cstheory.stackexchange.com/questions/48570/is-this-node-permutation-optimization-np-hard">related problem</a> pointed in the motivation of the original post is NP-hard. The proof is available in the Annex B of this paper: <a href="https://arxiv.org/pdf/2203.04774.pdf" rel="nofollow noreferrer">https://arxiv.org/pdf/2203.04774.pdf</a></p>

CC BY-SA 4.0
2022-12-02T22:22:41.003Z
Isn't the problem considered there defined slightly differently?  As stated it requires a *total order* of the vertices, whereas here the edges can be ordered so there is a directed cycle, which seems may be the best thing to do in some cases (e.g. if the graph is a cycle).
Neal Young
CC BY-SA 4.0
2022-12-04T10:01:24.697Z
@NealYoung you are right, I have mixed this topic with the one pointed in the motivation. Sorry about that, I edit my answer accordingly.
Alt-Tab
CC BY-SA 4.0
2022-12-02T19:52:11.200Z
2022-12-04T10:04:26.347Z
2022-12-04T10:04:26.347Z
Alt-Tab
<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{u\in V} ~\left( d_{out}(u) \right)^2$</span>, where <span class="math-container">$d_{out}$</span> is the number of out-neighbors.</p>
</blockquote>
<p><strong>Motivation:</strong> The problem is related to listing triangles in graphs. A motivation can be found <a href="https://cstheory.stackexchange.com/questions/48570">here</a> where the optimization problem is similar, but where the edge orientation needs to induce a DAG.<br />
One can observe that the DAG constraint is not necessary: the actual constraint in order to have a correct algorithm (i.e. an algorithm that will list all triangles) is that the edge orientation should not induce a cycle of length 3.<br />
I think that the constraint &quot;no induced cycle of length 3&quot; is too complicated and decided to formulate the above problem as a stepping stone.</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_{u\in V} (y_u)^2 &amp;\qquad  (IQP)\\
 \text{s.t.} &amp;\qquad \forall u \in V, \forall v \in N_u, x_{u,v}  \in \{0,1\}  \\
 &amp;\qquad \forall (u,v) \in E, x_{u,v}+x_{v,u}=1\\
 &amp;\qquad \forall u \in V, y_u=\sum_{v \in N_u} x_{u,v}\\
\end{align}</span>
with <span class="math-container">$N_u$</span> the set of neighbors of node <span class="math-container">$u$</span> in the input undirected graph.<br />
Is (IQP) NP-hard?<br />
It can be relaxed into the following Quadratic Programming:
<span class="math-container">\begin{align}
 \text{Minimize} &amp;\qquad \sum_{u\in V} (y_u)^2 &amp;\qquad  (QP)\\
 \text{s.t.} &amp;\qquad \forall u \in V, \forall v \in N_u, x_{u,v}  \in [0,1]  \\
 &amp;\qquad \forall (u,v) \in E, x_{u,v}+x_{v,u}=1\\
 &amp;\qquad \forall u \in V, y_u=\sum_{v \in N_u} x_{u,v}\\
\end{align}</span>
for which an optimal solution can be obtained in polynomial time using a quadratic programming solver as the objective is convex. Can an exact or approximate solution to (IQP) be obtained out of the (QP) solution? Using randomized rounding maybe?</p>
<p><strong>The greedy algorithm is not optimal:</strong> The algorithm &quot;fix some orientation then repeatedly flip the orientation of an edge that decrease the score&quot; is not optimal. The following is a counter example found by <a href="https://cstheory.stackexchange.com/users/60987/alt-tab">alt-tab</a>.</p>
<img src="https://i.sstatic.net/fbKNA.png" width="400" />

CC BY-SA 4.0
2021-03-12T22:40:33.763Z
related questions: https://cstheory.stackexchange.com/questions/48570  https://cstheory.stackexchange.com/questions/48571
maxdan94
CC BY-SA 4.0
2021-03-13T03:05:48.933Z
Thank you for the motivation and context, I find that helpful!
D.W.
CC BY-SA 4.0
2021-03-15T08:30:16.877Z
Have you looked at the following greedy scheme: "fix some orientation then repeatedly flip the orientation  of an edge that decrease the score"? Do you know cases where this is non optimal?
Louis
CC BY-SA 4.0
2021-03-15T11:28:08.253Z
Ah you think that this greedy algorithm is optimal? Arf maybe, let me check. I assumed it was not without actually checking it.
maxdan94
CC BY-SA 4.0
2021-03-15T12:59:28.090Z
I really don't know (haven't looked carefully) but this would be interesting to know. For its own sake but also because it might help understand what are the tricky cases to use in an eventual NP reduction.
Louis
CC BY-SA 4.0
2022-12-03T20:18:26.820Z
The fractional problem is connected to densest subgraph and decomposition.  The optimum solution has a nice interpretation and produces the dense subgraph decomposition. The integer version is connected to Nash-Williams forest covering theorem. For the integer version if one wants to minimize the max load then it can be solved in polynomial time but I am not sure about the quadratic objective.
Chandra Chekuri
CC BY-SA 4.0
2022-12-03T22:43:20.073Z
@ChandraChekuri it reduces to min-cost max flow..  See the answer I just added (currently last answer, no votes) if you are interested.
Neal Young
CC BY-SA 4.0
2022-12-03T23:05:40.207Z
@NealYoung  I have a recent paper on this topic http://chekuri.cs.illinois.edu/papers/DSG_NeuRIPS.pdf where we observe the reduction to min-cost flow for the fractional version among other results. I wasn't sure about the integer version. Looks like that also works. Will take a closer look.
Chandra Chekuri
CC BY-SA 4.0
2022-12-04T02:47:41.787Z
@ChandraChekuri, I merged my two answers. Now see Lemma 1 in my (only) answer below.  Note: the idea there of modeling a convex function by linear costs or constraints is an old one.  I vaguely remember it has been used for handling submodular functions (maybe by Lovasz?).  Let me know if you want me to track down a reference.
Neal Young
<graph-theory><graph-algorithms><np-hardness><optimization><integer-programming>
Is that edge orientation optimization problem NP-hard?
maxdan94
# Is that 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{u\in V} ~\left( d\_{out}(u) \right)^2$, where $d\_{out}$ is the number of out-neighbors.

**Motivation:** The problem is related to listing triangles in graphs. A motivation can be found [here](https://cstheory.stackexchange.com/questions/48570) where the optimization problem is similar, but where the edge orientation needs to induce a DAG.  
One can observe that the DAG constraint is not necessary: the actual constraint in order to have a correct algorithm (i.e. an algorithm that will list all triangles) is that the edge orientation should not induce a cycle of length 3.  
I think that the constraint "no induced cycle of length 3" is too complicated and decided to formulate the above problem as a stepping stone.

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

\begin{align}
\text{Minimize} &\qquad \sum\_{u\in V} (y\_u)^2 &\qquad (IQP)\\
\text{s.t.} &\qquad \forall u \in V, \forall v \in N\_u, x\_{u,v} \in \{0,1\} \\
&\qquad \forall (u,v) \in E, x\_{u,v}+x\_{v,u}=1\\
&\qquad \forall u \in V, y\_u=\sum\_{v \in N\_u} x\_{u,v}\\
\end{align}
with $N\_u$ the set of neighbors of node $u$ in the input undirected graph.  
Is (IQP) NP-hard?  
It can be relaxed into the following Quadratic Programming:
\begin{align}
\text{Minimize} &\qquad \sum\_{u\in V} (y\_u)^2 &\qquad (QP)\\
\text{s.t.} &\qquad \forall u \in V, \forall v \in N\_u, x\_{u,v} \in [0,1] \\
&\qquad \forall (u,v) \in E, x\_{u,v}+x\_{v,u}=1\\
&\qquad \forall u \in V, y\_u=\sum\_{v \in N\_u} x\_{u,v}\\
\end{align}
for which an optimal solution can be obtained in polynomial time using a quadratic programming solver as the objective is convex. Can an exact or approximate solution to (IQP) be obtained out of the (QP) solution? Using randomized rounding maybe?

**The greedy algorithm is not optimal:** The algorithm "fix some orientation then repeatedly flip the orientation of an edge that decrease the score" is not optimal. The following is a counter example found by [alt-tab](https://cstheory.stackexchange.com/users/60987/alt-tab).

![](https://i.sstatic.net/fbKNA.png)

**Tags:** graph-theory, graph-algorithms, np-hardness, optimization, integer-programming
> **Comments:**
> **username_0**: related questions: https://cstheory.stackexchange.com/questions/48570  https://cstheory.stackexchange.com/questions/48571  
> **username_1**: Thank you for the motivation and context, I find that helpful!  
> **username_2**: Have you looked at the following greedy scheme: "fix some orientation then repeatedly flip the orientation  of an edge that decrease the score"? Do you know cases where this is non optimal?  
> **username_0**: Ah you think that this greedy algorithm is optimal? Arf maybe, let me check. I assumed it was not without actually checking it.  
> **username_2**: I really don't know (haven't looked carefully) but this would be interesting to know. For its own sake but also because it might help understand what are the tricky cases to use in an eventual NP reduction.  
> **username_3**: The fractional problem is connected to densest subgraph and decomposition.  The optimum solution has a nice interpretation and produces the dense subgraph decomposition. The integer version is connected to Nash-Williams forest covering theorem. For the integer version if one wants to minimize the max load then it can be solved in polynomial time but I am not sure about the quadratic objective.  
> **username_4**: @ChandraChekuri it reduces to min-cost max flow..  See the answer I just added (currently last answer, no votes) if you are interested.  
> **username_3**: @NealYoung  I have a recent paper on this topic http://chekuri.cs.illinois.edu/papers/DSG_NeuRIPS.pdf where we observe the reduction to min-cost flow for the fractional version among other results. I wasn't sure about the integer version. Looks like that also works. Will take a closer look.  
> **username_4**: @ChandraChekuri, I merged my two answers. Now see Lemma 1 in my (only) answer below.  Note: the idea there of modeling a convex function by linear costs or constraints is an old one.  I vaguely remember it has been used for handling submodular functions (maybe by Lovasz?).  Let me know if you want me to track down a reference.  

---

## 3 answers

### Answer by username_4 on 2021-03-14. Score: 5

### Summary

1. OP's problem has a polynomial-time algorithm via reduction to min-cost bipartite matching. (Lemma 1, below.)
2. Alternatively, one can strengthen OP's relaxation QP directly, by modeling the cost more carefully, to make QP it into a linear program (LP) with no integrality gap, so that any basic feasible solution to the LP gives an optimal solution to the original program (IQP). (Lemma 2, below.)
3. An approximate solution to IQP can be obtained by randomized rounding: the natural randomized-rounding scheme gives a 2-approximation, and a $(1+1/\overline d)$-approximation in graphs with average degree $\overline d$. (Note that any connected graph has average degree at least $2-2/|V|$.) (Lemmas 4 and 5, below.)

---

### 1. Reduction to min-cost matching

**Lemma 1.** *The problem in the post has a polynomial-time algorithm via reduction to min-cost bipartite matching.*

*Proof of Lemma 1.* Given an instance $G=(V,E)$ of the problem in the post, the reduction constructs an edge-weighted bipartite graph $G'=(U, W, E')$ as follows.

1. For each edge $e\in E$, add a vertex $\alpha\_{e}$ to $U$.
2. For each vertex $v\in V$, add $d\_G(v)$ vertices $\beta^v\_1, \beta^v\_2, \ldots, \beta^v\_{d\_v}$ to $W$, where $d\_G(v)$ is the degree of $v$.
3. For each edge $e\in E$ and vertex $v\in e$, add edges $(\alpha\_e, \beta^v\_i)$ for $i\in[d\_G(v)]$ to $E'$. Give each edge $(\alpha\_e, \beta^v\_i)$ cost $i^2-(i-1)^2$.

The problem is then to find a minimum-cost maximum matching $M$ in $G'$, that is, a matching of minimum cost among those having exactly one edge incident to each vertex $\alpha\_e\in U$. This problem can be solved in polynomial time by standard algorithms for min-cost matching, or by reduction to min-cost flow. Clearly the reduction can be implemented in polynomial time.

To see that the reduction is correct, note that, given any orientation of the edges of $G$, there is a corresponding matching $M$: for each edge $e\in E$, match the vertex $\alpha\_e$ to the vertex $\beta^v\_i$, where $v\in e$ is the vertex that the oriented $e$ leaves, and $\beta^v\_i$ is chosen greedily to be the first not-already-matched vertex in $\beta^v\_1, \beta^v\_2, \ldots, \beta^v\_{d\_G(v)}$. Then $d\_{\text{out}}(v)$ of these vertices are matched, at total cost $\sum\_{i=1}^{d\_{\text{out}}(v)} i^2 - (i-1)^2$, which (as the sum telescopes) equals $d\_{\text{out}}(v)^2$, so the total cost of the matching $M$ in $G'$ equals $\sum\_{v\in V} d\_{\text{out}}(v)^2$, as desired.

Conversely, let $M$ be any matching in $G'$ among those with an edge incident to each vertex $\alpha\_e\in U$. Construct a corresponding orientation of $E$ as follows. For each edge $e\in E$, let $\beta^v\_i$ be the vertex that $\alpha\_e$ is matched to (so $v\in e$). Then orient $e$ out of $v$. The cost of $M$ is then at least $\sum\_{v\in V} d\_{\text{out}}(v)^2$, because in $M$ for each $v\in V$ there are $d\_{\text{out}}(v)$ edges matched to vertices in $\{\beta^v\_i : i\in d\_G(v)\}$, so (by the convexity of the function $i\mapsto i^2$) the cost of these edges in $M$ is at least $d\_{\text{out}}(v)^2$. So the cost $\sum\_{v\in V} d\_{\text{out}}(v)^2$ of the orientation is at most the cost of $M$, as desired.

It follows that, given a minimum-cost matching in $G'$, the corresponding orientation in $G$ minimizes $\sum\_{v\in V} d\_{\text{out}}(v)^2$, as desired. $~~~\Box$

---

### 2. Adjusting the quadratic program yields an LP with no integrality gap

Following the idea underlying Lemma 1, consider modifying OP's quadratic program by replacing the quadratic objective $\sum\_{u\in V} y\_u^2$ by $\sum\_{u\in V} f(y\_u)$, where $f(z)$ is the piecewise-linear function with integer breakpoints such that $f(z) = z^2$ for integer $z$. (Note that $z^2 < f(z)$ for non-integer $z$, yet $f$ is still convex, so this strengthens the relaxation.)

This modified program can in fact be formulated as a linear program by introducing additional non-negative variables $\{\Delta^u\_i : u\in V, i\in [d\_G(u)]\}$ to model the cost, as follows:

$$
\begin{align}
\text{minimize} & \sum\_{u\in V} \sum\_{i=1}^{d\_G(u)} (i^2-(i-1)^2)\Delta^u\_i \\
(\forall u\in V) & \sum\_{i=1}^{d\_G(u)} \Delta^u\_i \ge y\_u\\
& \vdots~~~~~(\text{the rest is the same as OP's program QP})
\end{align}
$$

**Lemma 2.** *The optimal basic feasible solutions to the above LP are 0/1 solutions.*

*Proof idea.* One can show that the LP equivalent to the (standard relaxation of) the matching problem in Lemma 1, in that the solutions of the two programs correspond by a correspondence that preserves cost, integrality, and the property of being a basic feasible solution. $~~~\Box$

---

### 3. Approximation ratio for randomized rounding of QP (Lemmas 3-5)

Here's the rounding scheme. Given a fractional solution $x$ for QP, define 0/1 solution $x'$ as follows: for each edge $(u,w)$ independently: take $x'\_{uw} = 1$ and $x'\_{wu}=0$ with probability $x\_{uw}$; otherwise take $x'\_{uw} = 0$ and $x'\_{wu} = 1$.

Let $f(x)$ be the objective function of QP.

**Lemma 3.** *For any feasible $x$,*
$$E[f(x')] = f(x) + 2\sum\_{(u,w)\in E} x\_{uw}x\_{wu} \le f(x) + |E|/2.$$

*Proof.* This is a standard calculation. Note that
$$f(x) = \sum\_{u\in V} \Big(
\sum\_{w\in N(u)} x^2\_{uw} + 2\sum\_{w'\in N(u), w'\ne w} x\_{uw}x\_{uw'}\Big)$$
and by linearity of expectation, the independence of $x'\_{uw}$ and $x'\_{uw'}$, and $E[x'^2\_{uw}] = x\_{uw}$,
$$E[f(x')] = \sum\_{u\in V} \Big(
\sum\_{w\in N(u)} x\_{uw} + 2\sum\_{w'\in N(u), w'\ne w} x\_{uw}x\_{uw'}\Big).$$
Using this and $x\_{uw} = 1 - x\_{wu}$,
$$
E[f(x')] - f(x)
= \sum\_{(u,w)\in E} x\_{uw} - x^2\_{uw} + x\_{wu} - x^2\_{wu}
= 2\sum\_{(u,w)\in E} x\_{uw} x\_{wu}.$$

**Lemma 4.** *For any feasible $x$, $E[f(x')] \le 2 f(x)$. That is, the rounding scheme gives a 2-approximation.*

*Proof.*
By inspection of the expansion of $f(x)$ in the proof of Lemma 3,
$$f(x) \ge \sum\_{(u,w)\in E} x^2\_{uw} + x^2\_{wu}.$$
Applying $p^2 + (1-p)^2 \ge 2p(1-p)$ for $p\in[0,1]$ (with $p=x\_{uw}$)
to each term gives
$$f(x) \ge 2\sum\_{(u,w)\in E} x\_{uw}x\_{wu}.$$
This and Lemma 3 imply $E[f(x')] \le f(x) + f(x) = 2 f(x)$. $~~~\Box$

The bound is tight in that for any graph with maximum degree 1,
the fractional solution $x\_{uw} = x\_{wu} = 1/2$ obtains value $|E|/2$,
but any integer solution has value $|E|$.
(Also note that $|E|$ is a lower bound on OPT,
using $\sum\_{u\in V} d^2\_{out}(v) \ge \sum\_{u\in V} d\_{out}(v) = |E|$.)

**Lemma 5.** *In any graph with average degree $\overline d = 2|E|/|V|$, the rounding scheme gives at least a $(1+1/\overline d)$-approximation.*

*Proof.* Fix an optimal solution. Let $d'\_v$ denote the out-degree of vertex $v$ in the optimal solution,
so $d'$ is a vector in $\mathbb R\_+^{|V|}$.
Let $\mathbf 1$ denote the all-ones vector in $\mathbb R^{|V|}$.
By [Cauchy-Schwarz](https://en.wikipedia.org/wiki/Cauchy%E2%80%93Schwarz_inequality),
$$\text{OPT} = d' \cdot d'
\ge (d' \cdot \mathbf 1)^2/(\mathbf 1\cdot \mathbf 1)
= \textstyle \big(\sum\_v d'\_v\big)^2/|V|
= |E|^2/|V| = |E|\overline d/2.$$
By this and Lemma 1
$$E[f(x')] \le f(x) + |E|/2 \le f(x) + \text{OPT} / \overline d \le \text{OPT}(1+1/\overline d).$$
$~~~\Box$

> **Comments:**
> **username_0**: Thanks a lot. Wonderful! I think $E[x'^2_{uw} = x_{uw}]$ should be  $E[x'^2_{uw}] = x_{uw}$. I do not understand why OPT is at least $|E|^2/|V|$.  
> **username_4**: Good catch.  I edited the post to explain.  

---

### Answer by username_2 on 2021-03-17. Score: 4

**Definition:** Given an undirected graph $G$ and an edge orientation $\vec{G}$, an unstable path is a directed path that goes from a node $s$ to a node $t$, such that the out-degree of node $s$ is strictly larger than the out-degree of node $t$ plus one. We observe that flipping the orientation of all edges along that path decreases the cost.

**Unstable path algorithm:** Start from an arbitrary edge orientation and as long as an unstable path exists flip the direction of all edges along that path.

**Theorem:** The unstable path algorithm is optimal and can be implemented to run in polynomial time.

**Proof:** If an unstable path exits, it can be found by running at most $n=|V|$ BFS and since flipping an unstable path decreases the cost, which is an integer bounded by $n^3$, the algorithm can be implemented in $O(n^6)$ time.

Clearly, there is no unstable path in an optimal orientation as flipping an unstable path decreases the cost. We thus only need to prove that if an orientation is stable (i.e. does not have an unstable path), then the orientation is optimal. We prove that any stable orientation has the same cost, which is thus optimal as an optimal orientation is stable.

Let $\vec{G\_1}$ and $\vec{G\_2}$ be two stable orientations of the same undirected graph $G$. We prove that the out-degree distribution of $\vec{G\_1}$ and $\vec{G\_2}$ are the same and thus they have the same cost.

We first define the notion of a $k$-level for an orientation $\vec{G}$. The $k$-level of $\vec{G}$ is the set of all nodes reachable (taking into account orientation) from a node with out-degree $k$ or more (in particular, it contains all nodes with out-degree $k$). In a stable graph, the $k$-level can only have nodes of out-degree $k-1$ or higher as each node in a $k$-level is reachable from some node with out-degree $k$ and there is no unstable path.

Now, let us prove that, for all $k$'s, the $k$-levels of $\vec{G\_1}$ and $\vec{G\_2}$ are equal. We prove that the $k$-level of $\vec{G\_1}$ is included in the one of $\vec{G\_2}$ and thus, by symmetry, they are equal. For a given $k$, let C be the set of nodes in the $k$-level of $\vec{G\_1}$ and in the $k$-level of $\vec{G\_2}$ and let $T$ be the set of nodes in the $k$-level of $\vec{G\_1}$ but not in the $k$-level of $\vec{G\_2}$. In $\vec{G\_2}$, there cannot be any edge from $C$ to $T$ as $T$ is not in the $k$-level of $\vec{G\_2}$. In $\vec{G\_1}$, any edge with source in $T$ has target in $C$ or $T$, these edges are also in $\vec{G\_2}$ some of them with source and target in $T$ can be reversed. If $T$ is not empty, then we have at least one edge in $\vec{G\_1}$ from $C$ to $T$ (and this edge is from $T$ to $C$ in $\vec{G\_2}$) or at least one node in $T$ with out-degree $k$, therefore the total number of edges starting in $T$ in $\vec{G\_2}$ is at least $|T|\times (k-1) + 1$ which means that at least one node in $T$ has out-degree $k$ which is impossible and thus $T$ is empty and the $k$-levels of $\vec{G\_1}$ and $\vec{G\_2}$ are equal.

We define a $k$-level node as a node in the $k$-level, but not in the $(k+1)$-level. An edge can only go from a $k$-level node to a $k'$-level node with $k'\geq k$, therefore since the $k$-levels are the same in $\vec{G\_1}$ and $\vec{G\_2}$, the number of edges starting from a $k$-level node is the same in $\vec{G\_1}$ and $\vec{G\_2}$ and since each $k$-level node has out-degree $k$ or $k-1$, the number of nodes with out-degree $k$ (resp. $k-1$) among the $k$-level nodes is the same in $\vec{G\_1}$ and $\vec{G\_2}$. We conclude that, as the $k$-level nodes are the same, the degree distribution of $\vec{G\_1}$ and $\vec{G\_2}$ are the same and they have the same cost.

> **Comments:**
> **username_0**: Wow!! Yes, I think your polynomial time algorithm is correct. Let me some time to make it sure. I think the proof can be made shorter and clearer.  
> **username_0**: The idea of unstable path is very nice, it makes me think of the [Ford-Fulkerson algorithm](https://en.wikipedia.org/wiki/Ford%E2%80%93Fulkerson_algorithm) for maxflow-mincut. Is there a link between the two problems?  
> **username_0**: I think this defines a new graph decomposition similar to [the k-core decomposition](https://en.wikipedia.org/wiki/Degeneracy_(graph_theory)) and [the density-friendly decomposition](https://papers-gamma.link/paper/7). I believe the decomposition is interesting by itself.  
> **username_2**: I also had in mind the Ford-Fulkerson but I haven't found the link between the two...   For the $k$-core decomposition I have heard about it in my life but I am not very familiar with the concept or its application but it does seem very related!  
> **username_0**: I don't understand the sentence "The k-level of G is the smallest S that contains all nodes with an out degree greater than k plus all the nodes pointed by a node in S.": is it a recursive definition in that a node of out-degree k can point another node that can point to another node? Have you tried a reductio ad absurdum: "Assume the graph is stable and not optimal"?  
> **username_0**: When you say "a path", it is a path in the directed graph, taking into account edge orientation (i.e. you cannot have an edge in the other direction along the path)?  
> **username_2**: The levels are indeed defined recursively. I have modified the definition to "a $k$-level contains all the nodes reachable (following orientation) from a node of degree higher or equal to $k$". When I say a path, I do take into account the orientation.  
> **username_2**: I lookedat the correlation between $k$-core and $k$-levels, we can probably get a bound on the $k$-coreness of a $k$-level node and vice-versa but we cannot deduce exactly the $k$-coreness of a node from its $k$-levelness and vice-versa.   Indeed:  in a $3$-clique, all nodes are $2$-core and are $1$-level;  with a $4$-clique plus a node $n$ with two edges towards nodes of the $4$-clique then $n$ is $2$-core but $n$ is $2$-level; if we have a $2$-cliques, the nodes are $1$-level ans $1$-core. Overall a node can be 1-level and 1 or 2-core and 2-core but 1 or 2-level.  
> **username_4**: @Louis, I accidentally down-voted your answer and the web site would not let me correct that until the post was edited. So I edited the post (making no actual change) just so I could change the down vote to an up vote. Please feel free to roll back the edit! Sorry about that. Also, note that I edited a new answer into my answer, describing a reduction to min-cost flow.  

---

### Answer by username_5 on 2022-12-02. Score: 1

Note that the [related problem](https://cstheory.stackexchange.com/questions/48570/is-this-node-permutation-optimization-np-hard) pointed in the motivation of the original post is NP-hard. The proof is available in the Annex B of this paper: <https://arxiv.org/pdf/2203.04774.pdf>

> **Comments:**
> **username_4**: Isn't the problem considered there defined slightly differently?  As stated it requires a *total order* of the vertices, whereas here the edges can be ordered so there is a directed cycle, which seems may be the best thing to do in some cases (e.g. if the graph is a cycle).  
> **username_5**: @NealYoung you are right, I have mixed this topic with the one pointed in the motivation. Sorry about that, I edit my answer accordingly.  

---

