Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
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 lover (resp. higher) ordering.
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:
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$.
To close a gap, I prove FNP-hardness (in fact, FETH-hardness)
of Max Cut in 3-regular graphs under deterministic reductions.
3-SAT to NAE-3SAT :
One variable is analogous to 3-coloring's palette. Similarly to how 3-coloring works,
flipping all truth-values does not affect NAE-satisfaction, so treat that constant as FALSE.
With that done, (x NAE y NAE local) and (z NAE false NAE not local) is a clause gadget.
NAE-3SAT to Max Cut in 3-regular graphs:
("parity" means evenness/oddness, whichever one the integer is.)
Each variable gadget is the result of taking [a pair of binary trees such that [the heights of the childless nodes in the pair of trees] all have the same parity] and putting an edge between
their roots. (For example, perfect binary trees whose heights have the same parity will work.)
Observe that those results are connected trees whose non-leaf nodes all have degree exactly 3.
In particular, they are connected and bipartite, so they have a unique maximum cut
and that cut includes every edge. For each such gadget, since the parities of the
distances from childless nodes to their root are the same and the roots are 1 away
from each other, that cut splits the leaves according to which root they are closer to.
Thus, with the choice between sides being arbitrary, the childless nodes closer to one
root are available as positive occurrences of the variable and the childless nodes
closer to the other root are available as negative occurrences of the variable.
In the resulting trees, the leaves are exactly the childless nodes, so those all have
degree exactly 1. Thus triangles using such nodes bring their degrees to exactly 3.
Notice that in a triangle, the size of a cut is 0 if the vertices are all on the same side and
is 2 otherwise. Finally, cap the remaining leaves like half (the halves are isomorphic)
of the 10-vertex cubic graph whose connect is 1. That makes the graph 3-regular.
Regardless of how the the rest of the graph is handled, for any given cap, cutting across
the 6 edges that are at less than two away from the leaf is the unique maximum extension
of the rest of the cut. Therefore, when T is [the number of edges in the variable gadgets]
plus [2 times the number of NAE-constraints] plus [6 times the number of caps],
no cut is larger than T, each NAE-satisfying assignment induces a cut of size T,
and for each cut of size T, the sides-of-the-cut of the
positive-side-of-variable-gadgets leaves form a NAE-satisfying assignment.
(One can use unbalanced and/or different-height trees to be more efficient, but even even when using perfect trees of the same height, the number of the number of leaves in a variable gadget
will be less than 4 times the number of occurrences of that variable, so the number of vertices
in a variable gadget will be less than 8 times the number of occurrences of that variable.
The constraint-gadgets do not change the number of vertices, the caps are constant-size,
and the number of them is at most the number of leaves. Therefore output size
is linear in input size, so the above reduction suffices for FETH-hardness too.)
