<p>The proof <a href="https://cstheory.stackexchange.com/questions/48571">here</a> also shows NP-hardness of the problem.<br />
It shows NP-hardness of the less constrained problem where we look for an orientation of the edges instead of an ordering of the nodes (that is the orientation of the edges does not have to induce a DAG) by reduction to NAE3SAT.<br />
Observe that in the constructed graph, a minimum edge orientation does not have any cycle when there is a NAE3SAT solution. That minimum edge orientation thus induces a DAG showing NP-hardness of the node ordering version.</p>

CC BY-SA 4.0
2021-03-16T14:13:00.003Z
2021-03-16T15:47:47.247Z
2021-03-16T15:47:47.247Z
maxdan94
<p>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.</p>

<p>Thus, $\sum\limits_{v\in V}|succ(v)|\times|pred(v)| = 2n_{\text{split}}$ where $n_{\text{split}}$ is the number of split vertices.</p>

<p>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.</p>

<p>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.</p>

<p><strong>Theorem</strong> 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$.</p>

<p><strong>First direction</strong></p>

<p>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: </p>

<ol>
<li>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$.</li>
<li>Tentatively add all split vertices (under the ordering) into $A$.</li>
<li>Repeat steps 4 and 5 until step 4 fails:</li>
<li>Identify a split vertex $v$ that has more neighbors in its current set ($A$ or $B$) than in the other</li>
<li>Move $v$ to the other set</li>
</ol>

<p>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. </p>

<p>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$).</p>

<p>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$. </p>

<p>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$.</p>

<p><strong>Second direction</strong></p>

<p>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$.</p>

<p>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$.</p>

<p>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$.</p>

CC BY-SA 3.0
2017-05-23T08:32:58.730Z
Sure. According to ISGCI (http://www.graphclasses.org/classes/gc_1100.html), cubic Max Cut is NP-complete due to the paper "On some tighter inapproximability results" by P. Berman and M. Karpinski.
Mikhail Rudoy
CC BY-SA 3.0
2017-05-24T05:29:15.343Z
Thanks for pointing that out! I have to say, I'm surprised and disappointed by ISGCI :(. I am not aware of a proof of hardness for Cubic Max Cut from the literature. However, I can think of a very simple reduction from Max-Degree-3 Max Cut to Cubic Max Cut and ISGCI says that Max-Degree-3 Max Cut is NP-complete. The source listed for this is "Node- and edge-deletion NP-complete problems" by "M. Yannakakis", but I have not yet verified that it contains a correct proof of NP-hardness for Max-Degree-3 Max Cut. If you think I should, I can edit my answer to reflect this state of things.
Mikhail Rudoy
CC BY-SA 3.0
2017-05-23T07:36:49.663Z
2017-05-23T07:36:49.663Z
Mikhail Rudoy
<p>Could you help me to prove that the following problem is NP-hard?</p>

<p><strong>Problem.</strong> Given an undirected graph <span class="math-container">$G=(V,E)$</span>, find an ordering of the nodes such that <span class="math-container">$\sum\limits_{v\in V}|succ(v)|\times|pred(v)|$</span> is minimum.</p>

<p>Given an ordering on the nodes and a node <span class="math-container">$v\in V$</span>, <span class="math-container">$pred(v)$</span> (resp. <span class="math-container">$succ(v)$</span>) denotes the set of neighbors of <span class="math-container">$v$</span> with lower (resp. higher) ordering.</p>

CC BY-SA 4.0
2020-06-13T21:12:24.937Z
That quantity is an upper bound of the time to list all triangles in the input graph using a certain algorithm: https://papers-gamma.link/paper/32
If you minimize it, you may make the algorithm more efficient.
maxdan94
CC BY-SA 4.0
2021-03-15T20:03:18.030Z
The constant factor approximation version: https://cstheory.stackexchange.com/questions/47020
maxdan94
CC BY-SA 4.0
2021-03-18T19:56:13.437Z
related: https://mathoverflow.net/questions/383368
maxdan94
<graph-theory><np-hardness><permutations>
Is this vertex ordering optimization NP-Hard?
maxdan94
# Is this vertex ordering optimization NP-Hard?

(Asked by: username_0 on 2017-05-22)

Could you help me to prove that the following problem is NP-hard?

**Problem.** Given an undirected graph $G=(V,E)$, find an ordering of the nodes such that $\sum\limits\_{v\in V}|succ(v)|\times|pred(v)|$ is minimum.

Given an ordering on the nodes and a node $v\in V$, $pred(v)$ (resp. $succ(v)$) denotes the set of neighbors of $v$ with lower (resp. higher) ordering.

**Tags:** graph-theory, np-hardness, permutations

> **Comments:**
> **username_0**: That quantity is an upper bound of the time to list all triangles in the input graph using a certain algorithm: https://papers-gamma.link/paper/32 If you minimize it, you may make the algorithm more efficient.  
> **username_0**: The constant factor approximation version: https://cstheory.stackexchange.com/questions/47020  
> **username_0**: related: https://mathoverflow.net/questions/383368  

---

## 2 answers

### Answer by username_1 on 2017-05-23. Score: 10 | Accepted answer

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:

1. 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$.
2. Tentatively add all split vertices (under the ordering) into $A$.
3. Repeat steps 4 and 5 until step 4 fails:
4. Identify a split vertex $v$ that has more neighbors in its current set ($A$ or $B$) than in the other
5. 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$.

> **Comments:**
> **username_1**: Sure. According to ISGCI (http://www.graphclasses.org/classes/gc_1100.html), cubic Max Cut is NP-complete due to the paper "On some tighter inapproximability results" by P. Berman and M. Karpinski.  
> **username_1**: Thanks for pointing that out! I have to say, I'm surprised and disappointed by ISGCI :(. I am not aware of a proof of hardness for Cubic Max Cut from the literature. However, I can think of a very simple reduction from Max-Degree-3 Max Cut to Cubic Max Cut and ISGCI says that Max-Degree-3 Max Cut is NP-complete. The source listed for this is "Node- and edge-deletion NP-complete problems" by "M. Yannakakis", but I have not yet verified that it contains a correct proof of NP-hardness for Max-Degree-3 Max Cut. If you think I should, I can edit my answer to reflect this state of things.  

---

### Answer by username_0 on 2021-03-16. Score: 1

The proof [here](https://cstheory.stackexchange.com/questions/48571) also shows NP-hardness of the problem.  
It shows NP-hardness of the less constrained problem where we look for an orientation of the edges instead of an ordering of the nodes (that is the orientation of the edges does not have to induce a DAG) by reduction to NAE3SAT.  
Observe that in the constructed graph, a minimum edge orientation does not have any cycle when there is a NAE3SAT solution. That minimum edge orientation thus induces a DAG showing NP-hardness of the node ordering version.


---

