5
$\begingroup$

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?

$\endgroup$
3
  • 1
    $\begingroup$ related: cstheory.stackexchange.com/questions/48572/… $\endgroup$
    – Neal Young
    Mar 14 at 22:36
  • $\begingroup$ @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? $\endgroup$
    – maxdan94
    Mar 15 at 15:49
  • 1
    $\begingroup$ 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?) $\endgroup$
    – Neal Young
    Mar 15 at 15:55
4
$\begingroup$

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.

Triangle gadget

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.

$\endgroup$
8
  • 1
    $\begingroup$ 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: cstheory.stackexchange.com/questions/38274 am I correct? $\endgroup$
    – maxdan94
    Mar 14 at 20:35
  • $\begingroup$ 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. $\endgroup$
    – Louis
    Mar 14 at 21:42
  • $\begingroup$ 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? $\endgroup$
    – maxdan94
    Mar 14 at 22:01
  • 1
    $\begingroup$ (@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.) $\endgroup$
    – Neal Young
    Mar 15 at 15:57
  • 1
    $\begingroup$ 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. $\endgroup$
    – kerzol
    Mar 17 at 11:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.