# Digraph problem relating in- and out-degrees

Given a digraph $D = (V, A)$ and $m \in \mathbb{N}$, the question is is there a subset $A' \subseteq A$, such that $\lvert A' \rvert \geq m$ and $d_{D'}^+(u) \leq d_{D'}^-(v)$ holds for every arc $(u, v) \in A'$ in the subgraph $D' = (V, A')$, i.e. the out-degree of $u$ is not larger than the in-degree of $v$? Note that the degree constraints should hold in the subgraph $D'$.

This seems like a straight-forward problem, alas I am unable to connect it to some more familiar graph problem. I am mostly interested in its complexity.

There is a formulation of this as integer linear programming (ILP). There is no theoretical guarantee that the resulting ILP will be solvable in polytime, but off-the-shelf ILP solvers are pretty good, and I wouldn't be surprised if in practice an ILP solver is often effective at solving this problem.

In particular, for each edge introduce a variable $x_e$, with the intention that $x_e=1$ means that $e \in A'$ and $x_e=0$ means that $e \notin A'$. Then we get the obvious constraints $0 \le x_e \le 1$ and $\sum_e x_e \ge m$. Also introduce a variable $y_e$ for each edge $e \in A$, defined as

$$y_{(u,v)} = \sum_t x_{(t,v)} - \sum_w x_{(u,w)}.$$

Notice that $y_{(u,v)} = d^-_{D'}(v) - d^+_{D'}(u)$.

Now we want to express the requirement that if $x_e=1$ then we must have $y_e\ge 0$. One way to do this is to introduce the variables $y^+_e, y^-_e$ and add the linear inequalities $y_e = y^+_e-y^-_e$, $y^+_e \ge 0$, $y^-_e \ge 0$, $y^-_e \le c \cdot (1-x_e)$, where here $c$ is a large constant (setting $c=|V|$ is large enough). Notice that if $x_e=1$, then these constraints imply $0 \le y^-_e \le c \cdot 0 = 0$, i.e., $y^-_e=0$, which implies that $y_e \ge 0$. In contrast, if $x_e=0$, then these constraints imply $0 \le y^-_e \le c$, which will always be satisfied (the difference of two degrees cannot be more than $|V|$, for trivial reasons), so if $x_e=0$, there are effectively no restrictions on the allowable values of $y_e$, just as we wanted.

There will be a feasible solution to this ILP if and only if there is a subset $A'$ satisfying the desired properties.

My thanks to @user12537, who pointed out that my original answer was flawed. This revision attempts to address those problems.

• The following comment is from @user12537, who submitted it as an edit to the anwer. "This does not work, since the inequality compares in- and out-degree of some node $v\in V$, but this is not required. A witness would be the yes-instance $((\{u,v\},\{(u,v)\}),1)$, which has no feasible solution in your programm." – David Richerby Jan 3 '14 at 16:44
• @user12537 is absolutely correct. I've edited my answer to fix this. Thank you, user12537, for pointing out the flaw in the previous version of this answer! – D.W. Jan 4 '14 at 4:47