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{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 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.

$\endgroup$
5
  • $\begingroup$ related questions: cstheory.stackexchange.com/questions/48570 cstheory.stackexchange.com/questions/48571 $\endgroup$ – maxdan94 Mar 12 at 22:40
  • $\begingroup$ Thank you for the motivation and context, I find that helpful! $\endgroup$ – D.W. Mar 13 at 3:05
  • 1
    $\begingroup$ 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? $\endgroup$ – Louis Mar 15 at 8:30
  • $\begingroup$ Ah you think that this greedy algorithm is optimal? Arf maybe, let me check. I assumed it was not without actually checking it. $\endgroup$ – maxdan94 Mar 15 at 11:28
  • 1
    $\begingroup$ 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. $\endgroup$ – Louis Mar 15 at 12:59
3
$\begingroup$

We answer OP's last question: can an approximate solution to IQP be obtained by randomized rounding?

We show that 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|$.)

For the record, 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 1. 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 2. 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 1, $$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 1 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 3. 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, $$\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$

$\endgroup$
2
  • $\begingroup$ 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|$. $\endgroup$ – maxdan94 Mar 14 at 23:01
  • 1
    $\begingroup$ Good catch. I edited the post to explain. $\endgroup$ – Neal Young Mar 15 at 2:30
2
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ 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. $\endgroup$ – maxdan94 Mar 17 at 14:42
  • $\begingroup$ The idea of unstable path is very nice, it makes me think of the Ford-Fulkerson algorithm for maxflow-mincut. Is there a link between the two problems? $\endgroup$ – maxdan94 Mar 17 at 14:43
  • 1
    $\begingroup$ 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! $\endgroup$ – Louis Mar 17 at 16:44
  • 1
    $\begingroup$ 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. $\endgroup$ – Louis Mar 19 at 11:09
  • 1
    $\begingroup$ 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. $\endgroup$ – Louis Mar 19 at 11:16

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.