3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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." $\endgroup$ – David Richerby Jan 3 '14 at 16:44
  • $\begingroup$ @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! $\endgroup$ – D.W. Jan 4 '14 at 4:47

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.