Finding a subgraph satisfying degree constraints in a directed graph

Question

We are given a directed graph $D=(V,A)$ and two values $i(v)$ and $o(v)$ for each vertex. Is it NP-hard to find an induced subgraph of $D$ such that the in degrees are at most $i(v)$ and the out degrees are at least $o(v)$ for each vertex in the subgraph?

Answer 1

This is only an answer to the non-induced version of the problem

We can begin by turning this into an undirected graph problem. Replace each vertex $v$ by two vertices $v^+$ and $v^-$; replace each directed edge $(v,w)$ by an undirected edge $v^+w^-$. This gives a bipartite graph $G$ representing $D$, and our goal is to find a subgraph $H$ of $G$ such that

• For each $v \in V$, $\deg_H(v^+) \ge o(v)$;
• For each $v \in V$, $\deg_H(v^-) \le i(v)$.

Note that if a solution exists, then there is a solution in which $\deg_H(v^+) = o(v)$ exactly for all $v \in V$: just remove arbitrary excess edges from each $v^+$.

Next, we can rephrase this as a network flow problem. Add a source $s$ and a sink $t$, with the following arcs and capacities:

• An arc $(s,v^-)$ with capacity $i(v)$ for all $v \in V$.
• An arc $(v^-, w^+)$ with capacity $1$ for all edges $v^-w^+$.
• An arc $(v^+,t)$ with capacity $o(v)$ for all $v \in V$.

Then the subgraph $H$ we want (and the further constraint $\deg_H(v^+) = o(v)$ for all $v \in V$) corresponds exactly to an integer $s-t$ flow with value $\sum_{v \in V} o(v)$: the edges of $H$ correspond to the arcs not involving $s$ or $t$ that have flow. Since all the capacities are integers, if we use Ford–Fulkerson (or pretty much any alternative you like) to find a maximum flow, it will be an integer flow - so we will find an $H$, if it exists.

Answer 2

The problem is NP-hard by a reduction of the CNF-SAT problem. The basic idea is to create a big cycle of out-degree constraints so all needed constraints are realized.

Let $n$ be the number of variables and $C$ be the set of clauses. The reduced directed graph consists of $2n + |C|$ "levels" $(L_i)_i$. Arcs between levels $\{ (u, v) \mid 1 \le i \le |L|, u \in L_i, v \in L_{(i \bmod |L|) + 1} \}$ are added to form a big cycle.

For $1 \le i \le n$, denote $L_{2i-1} = \{ s_i \}$ and $L_{2i} = \{ x_i, \overline{x}_i \}$, representing a variable selection. Let $i(s_i) = i(x_i) = i(\overline{x}_i) = 1$. Out-degree constraints are defined later.

For $1 \le i \le |C|$, denote $L_{2n+i} = \{c_i\}$, representing a clause. Let $i(c_i) = |C_i|$. Then, add arcs $\{ (x, c_i) \mid x \in C_i\}$, where $x$ is a vertex $\overline{x}_i$ if the variable $i$ occurs positively, and $x_i$ if the variable $i$ occurs negatively. The maximum in-degree constraint ensures not all vertices from the clause are selected, so the clause is satisfied.

For a selection vertex $s_i$, we set $o(s_i) = 1$. For all other vertex $u$, $o(u)$ is set to be the out-degrees in the resulting directed graph. This ensures exactly one vertex from each level is used.