8
$\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$
9
  • $\begingroup$ related questions: cstheory.stackexchange.com/questions/48570 cstheory.stackexchange.com/questions/48571 $\endgroup$
    – maxdan94
    Commented Mar 12, 2021 at 22:40
  • $\begingroup$ Thank you for the motivation and context, I find that helpful! $\endgroup$
    – D.W.
    Commented Mar 13, 2021 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
    Commented Mar 15, 2021 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
    Commented Mar 15, 2021 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
    Commented Mar 15, 2021 at 12:59

3 Answers 3

5
$\begingroup$

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, $$\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
    Commented Mar 14, 2021 at 23:01
  • 1
    $\begingroup$ Good catch. I edited the post to explain. $\endgroup$
    – Neal Young
    Commented Mar 15, 2021 at 2:30
4
$\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$
9
  • $\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
    Commented Mar 17, 2021 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
    Commented Mar 17, 2021 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
    Commented Mar 17, 2021 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
    Commented Mar 19, 2021 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
    Commented Mar 19, 2021 at 11:16
1
$\begingroup$

Note that the related problem 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

$\endgroup$
2
  • 1
    $\begingroup$ 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). $\endgroup$
    – Neal Young
    Commented Dec 2, 2022 at 22:22
  • $\begingroup$ @NealYoung you are right, I have mixed this topic with the one pointed in the motivation. Sorry about that, I edit my answer accordingly. $\endgroup$
    – Alt-Tab
    Commented Dec 4, 2022 at 10:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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